[C++] BOJ(백준) 3114 사과와 바나나

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

3114번: 사과와 바나나

 

DP와 누적합 문제다.

 

불도저가 왼쪽 위에서 오른쪽 아래까지 가는 길에 아래 부분은 사과가 많도록 윗 부분은 바나나가 많도록 지나가야 한다.

불도저는 오른쪽, 아래쪽, 오른쪽 아래 대각선으로 움직일 수 있다.

 

열을 기준으로 생각을 했다.

아래로 가는 경우에는 아래 칸이 사과인지만 확인해서 빼주면 되고

오른쪽 혹은 대각선으로 움직이는 경우는 그 열에 대해 위의 바나나나 아래 사과만 확인해주면 된다.

 

이 규칙을 찾고 처음으로 적용했던게 BFS다.

그래프만 보면 BFS밖에 안떠올라서 시간초과가 날 걸 알지만 일단 진행했다.

시간초과다ㅋ

 

BFS는 해당 칸을 기준으로 다음 칸을 움직이는 것이고,

DP는 이전 칸을 이용해 해당 칸의 최적 값을 찾는 방법이므로

이전 세 칸에서 해당 칸 까지 오는 것을 고려해보려 했으나 시간 차이가 없을 것 같았다.

 

그래서 생각한 방법이 누적합이다.

각 열 별로 아래로 내려가면서 사과와 바나나 개별 누적합을 계산했다. (전처리 느낌)

1행과 1열은 갈 수 있는 방법이 각각 아래와 오른쪽 밖에 없으므로 별도의 계산을 했다.

2행 2열 부터는 이전 세 칸에서 현재 위치까지 오면서 변한 값을 계산해주고 세 개 중 MAX 값을 찾았다.

 

사전 누적합을 이용해 매번 열을 반복하며 계산해야 하는 불필요함이 줄었다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int n, m;
int a[1501][1501];
int b[1501][1501];
int apple[1501][1501];
int banana[1501][1501];
int dp[1501][1501];

int main() {
	// 입출력 속도 향상을 위함
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char x; int n;
			cin >> x >> n;
			if (x == 'A') a[i][j] = n;
			else b[i][j] = n;
		}
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			apple[i][j] = apple[i - 1][j] + a[i][j];
			banana[i][j] = banana[i - 1][j] + b[i][j];
		}

	for (int i = 1; i <= n; i++) dp[i][1] = apple[n][1] - apple[i][1];
	for (int i = 1; i <= m; i++) dp[1][i] = dp[1][i - 1] + apple[n][i] - apple[1][i];

	for (int i = 2; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j] - (apple[i][j] - apple[i - 1][j]));
			dp[i][j] = max(dp[i][j], dp[i][j - 1] + banana[i - 1][j] + (apple[n][j] - apple[i][j]));
			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + banana[i - 1][j] + (apple[n][j] - apple[i][j]));
		}
	}
	cout << dp[n][m];
}