[백준/BOJ] 백준 3114번 : 사과와 바나나

https://www.acmicpc.net/problem/3114

3114번: 사과와 바나나

 

사과의 개수와 바나나의 개수를 각각 2차원 배열에 표시해 놓고 사과의 경우 열마다 누적합을 저장하고, 바나나의 경우 행마다 누적합을 저장해 놓은 뒤, 불도저의 출발 지점인 왼쪽 위부터 도착 지점인 오른쪽 아래까지 이동하며 아래쪽의 사과와 위쪽의 바나나 개수의 최대 합을 다이나믹 프로그래밍(DP)을 통해 계산했다.

이때 불도저가 움직이면서 추가되는 범위의 사과의 개수와 바나나의 개수는 이전에 저장해 놓은 누적합을 이용해 계산했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int r, c;
vector<vector<int>> cache(1505, vector<int>(1505, -1));
vector<vector<int>> a_board(1505, vector<int>(1505, 0));
vector<vector<int>> b_board(1505, vector<int>(1505, 0));
vector<vector<int>> a_psum(1505, vector<int>(1505, 0));
vector<vector<int>> b_psum(1505, vector<int>(1505, 0));


int Solve(pair<int, int> here) {
	int& ret = cache[here.first][here.second];

	if (ret != -1) {
		return ret;
	}

	ret = 0;

	pair<int, int> there;
	int a_cnt;
	int b_cnt;

	//아래로 가는 경우
	if (here.first + 1 <= r) {
		there = make_pair(here.first + 1, here.second);

		//b지역 바나나 추가
		b_cnt = b_psum[here.first][c] - b_psum[here.first][here.second];

		ret = max(ret, Solve(there) + b_cnt);
	}

	//오른쪽 아래 대각선으로 가는 경우
	if (here.first + 1 <= r && here.second + 1 <= c) {
		there = make_pair(here.first + 1, here.second + 1);

		//a지역 사과 추가
		a_cnt = a_psum[r][here.second] - a_psum[here.first][here.second];
		//b지역 바나나 추가
		b_cnt = b_psum[here.first][c] - b_psum[here.first][here.second];

		ret = max(ret, Solve(there) + a_cnt + b_cnt);
	}

	//오른쪽으로 가는 경우
	if (here.second + 1 <= c) {
		there = make_pair(here.first, here.second + 1);

		//a지역 사과 추가
		a_cnt = a_psum[r][here.second] - a_psum[here.first][here.second];

		ret = max(ret, Solve(there) + a_cnt);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c;

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			string input;
			cin >> input;

			int num = stoi(input.substr(1, input.size() - 1));

			if (input[0] == 'A') {
				a_board[i][j] = num;
			}

			else {
				b_board[i][j] = num;
			}
		}
	}

	//열마다 사과의 누적합을 구한다
	for (int j = 1; j <= c; j++) {
		for (int i = 1; i <= r; i++) {
			a_psum[i][j] = a_board[i][j] + a_psum[i - 1][j];
		}
	}

	//행마다 바나나의 누적합을 구한다
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			b_psum[i][j] = b_board[i][j] + b_psum[i][j - 1];
		}
	}

	cout << Solve(make_pair(1, 1));

	return 0;
}