백준 3114 / C++

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

3114번: 사과와 바나나

 

[ 풀이 ]

dp[i][j]를 (i,j)까지 왔을 때 합의 최댓값이라 하자. 

dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]에서 올 수 있다.

앞의 두 경우는 이전dp값에다 현재 (i,j)에서 위아래로 바나나와 사과개수를 더해주면 된다.

이미 각 열에 대한 바나나의 합과 사과의 합을 전처리해놓자.

dp[i][j-1]에서 오는 경우는 만약 (i,j)가 사과였다면 그것만큼 감소시켜주면 된다.

1행 또는 1열은 (1,1)에서 만드는 길의 방법이 1가지이므로 전처리해놓자.

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int r, c, ba[1505][1505], ap[1505][1505];
int psum1[1505][1505], psum2[1505][1505], dp[1505][1505];

// (x,y)에서 바나나+사과 개수
int sum(int x, int y) {
	return psum1[y][x - 1] + psum2[y][r] - psum2[y][x];
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> r >> c;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			char x; int n;
			cin >> x >> n;
			if (x == 'B') ba[i][j] = n;
			else ap[i][j] = n;
		}
	}
	//전처리
	for (int j = 1; j <= c; j++) {
		for (int i = 1; i <= r; i++) {
			psum1[j][i] = psum1[j][i - 1] + ba[i][j]; // 바나나
			psum2[j][i] = psum2[j][i - 1] + ap[i][j]; // 사과
		}
	}
	// 1열
	for (int i = 1; i <= r; i++) {
		dp[i][1] = psum2[1][r] - psum2[1][i];
	}
	// 1행 
	for (int j = 2; j <= c; j++) {
		dp[1][j] = dp[1][j - 1] + psum2[j][r] - psum2[j][1];
	}

	for (int i = 2; i <= r; i++) {
		for (int j = 2; j <= c; j++) {
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1]) + sum(i, j);
			dp[i][j] = max(dp[i][j], dp[i - 1][j] - ap[i][j]);
		}
	}
	cout << dp[r][c] << '\n';
}