[BAEKJOON] 3114번 사과와 바나나

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

3114번: 사과와 바나나

문제조건

1. 아래(↓), 오른쪽(→), 오른쪽아래(↘)로 갈수 있는 불도저가있고, 오른쪽 맨 아래칸까지 이동한다.
2. A(불도저  아래쪽, 사과), B(불도저 위쪽, 바나나) 사과와 바나나의 합의 최댓값의 경우는?

처음 문제를 봤을땐, 탐색을 진행하는 경우의 수인것같아서 BFS로 접근했다.

하지만 이 접근방법은 최소일때 구하기 용이한 방법으로 생각을 좀더 했다.

우선 Brute Force를 떠올렸는데, 각각의 영역에 대해서 경우의 수를 생각하고, 또 그 경우의 수안에서 영역의 합을 구하는  식으로 접근하면 시간복잡도가 무려 O(n^6)으로 시간초과가 날 것이 분명했다.

그래서 나는 배열을 A,B에 대해서 입력받고, 그 배열을 누적합배열로 미리 바꾸는 것을 생각했다.

dp[i][j] = i행, j열까지 불도저가 진행했을때,  (1,1) 부터 (i,j) 까지 사각형안에서 사과와 바나나의 합의 최댓값. 

각 누적합에 대해 사과와 바나나의 최댓값을 구하기 위해 dp배열을 선언했다. 이제 문제조건1  을 구현할 차례다.

dp 배열을 채워주기위해 불도저가 극단적으로 아래로만 가는 경우와 오른쪽으로 가는 경우에 대해서 계산해준후, 다음 세가지 경우의 수룰 구현했다.

• 아래(↓) 로 이동할때

dp배열 정의에 따라서 B(바나나)는 위쪽에 위치하고 있기때문에 전혀 신경쓸 필요없다. 

다만 아래로 이동하기 전인 dp[i-1][j]에서의 값에서 원래 a[i][j]의 값을 뺀경우 dp[i][j]가 커진다면 갱신한다.

• 오른쪽(→)

이 경우는 사각형이 가로로 커지므로 A, B 모두 dp배열의 값에 영향을 미친다.

이때도 변경된 값이 원래 dp[i][j]보다 크다면 최댓값을 갱신해준다.

• 오른쪽아래(↘)

오른쪽(→)의 경우와 똑같다. 아래로 이동해서 A가 없어지는 경우는 고려안해줘도 되냐?

☞ 위에서 두 경우에 대해서는 모두 계산해줬으므로, dp[i-1][j-1]과의 비교만 해주면 된다.

 

소스코드

#include <vector>
#include <iostream>
#define MAX 1501
using namespace std;
char tree;
int R, C, a[MAX][MAX], b[MAX][MAX], dp[MAX][MAX];
int main() {
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			int cnt;
			cin >> tree >> cnt;
			if (tree == 'A') a[i][j] = cnt;
			else b[i][j] = cnt;
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			a[i][j] += a[i][j - 1];
			b[i][j] += b[i][j - 1];
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			a[i][j] += a[i - 1][j];
			b[i][j] += b[i - 1][j];
		}
	}
	//불도저가 일직선으로만 간경우
	for (int i = 1; i <= R; i++) dp[i][1] = a[R][1] - a[i][1];
	for (int i = 1; i <= C; i++) dp[1][i] = a[R][i] - a[1][i];

	for (int i = 2; i <= R; i++) {
		for (int j = 2; j <= C; j++) {
			//오른쪽으로 움직일때
			dp[i][j] = max(dp[i][j], dp[i][j - 1] + a[R][j] - a[R][j - 1] - a[i][j] + a[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1]);
			//아래로 움직일때(B는 상관없어짐)
			dp[i][j] = max(dp[i][j], dp[i - 1][j] - (a[i][j] - a[i][j-1] - a[i - 1][j] + a[i - 1][j - 1]));
			//오른쪽 아래로 움직일때
			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[R][j] - a[R][j - 1] - a[i][j] + a[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1]);
		}
	}
	cout << dp[R][C];

}

 

굿