BOJ 3114 - 사과와 바나나

www.acmicpc.net/problem/3114

3114번: 사과와 바나나

 

DP 와 누적합을 이용해서 풀어야 하는 문제이다.

 

불도저가 이동할 수 있는 방향은 오른쪽, 아래쪽, 대각선 오른쪽 아래 이렇게 3가지 인데,

각각의 경우에 대해서, 최대 누적합을 뽑아낼 수 있는 점화식이 필요하다.

 

사과에 대한 누적합과 바나나에 대한 누적합이 따로 있어야하기 때문에,

배열을 따로 따로 만들어서 선언해준다 (apple[][], banana[][])

 

dp 배열을 채우기 전에, 일련의 전처리 작업이 필요한데,

우측으로 이동해서 누적합을 채우는 작업과

아래쪽으로 이동하면서 누적합을 채우는 작업으로 apple 배열과 banana 배열을 초기화 해준다.

또한, dp 배열의 1행과 1열에 대한 초기화 작업을 해준다

(이는, (1,1) 에서 출발하는 불도저가 오른쪽으로만 쭉 이동한후 내려가는 경우와 아래쪽으로만 쭉 이동한 후, 오른쪽으로 이동하는 그런 케이스에 대한 사전 작업을 해주기 위해서다)

 

이 문제에 대한 점화식은 다음과 같다

 

1) 오른쪽으로 이동하는 경우

dp[i][j] = max(dp[i][j], dp[i][j - 1] + apple[R][j] - apple[R][j - 1] - apple[i][j] + apple[i][j - 1] + banana[i - 1][j] - banana[i - 1][j - 1])

 

2) 아래쪽으로 이동하는 경우

dp[i][j] = max(dp[i][j], dp[i - 1][j] - (apple[i][j] - apple[i][j - 1] - apple[i - 1][j] + apple[i - 1][j - 1]))

 

=> banana 를 쓰지 않은건, 이 케이스는 위에서 아래로 내려오는 경우이므로, 바나나의 경우 문제에서 불도저의 위치 기준 위쪽이라 했으므로, 포함시킬 필요가 없다

 

3) 대각선 오른쪽 아래로 이동하는 경우

dp[i][j] = max(dp[i - 1][j - 1], dp[i][j - 1] + apple[R][j] - apple[R][j - 1] - apple[i][j] + apple[i][j - 1] + banana[i - 1][j] - banana[i - 1][j - 1])

 

- C++

#include <iostream>
 
#define MAX 1502
 
using namespace std;
 
int R, C;
int apple[MAX][MAX], banana[MAX][MAX], dp[MAX][MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> R >> C;
    
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            char ch;
            int num;
            
            cin >> ch >> num;
            
            if (ch == 'A') apple[i][j] = num;
            else if (ch == 'B') banana[i][j] = num;
        }
    }
    
    // 전처리 (우측 누적합 계산) 
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            apple[i][j] += apple[i][j - 1];
            banana[i][j] += banana[i][j - 1];
        }
    }
    
    // 전처리 (아래 누적합 계산)
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            apple[i][j] += apple[i - 1][j];
            banana[i][j] += banana[i - 1][j];
        }
    } 
    
    // 전처리 (1행 초기화) 
    for (int j = 1; j <= C; ++j) dp[1][j] = apple[R][j] - apple[1][j];
    
    // 전처리 (1열 초기화)
    for (int i = 1; i <= R; ++i) dp[i][1] = apple[R][1] - apple[i][1]; 
    
    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] + apple[R][j] - apple[R][j - 1] - apple[i][j] + apple[i][j - 1]
                           + banana[i - 1][j] - banana[i - 1][j - 1]);
            
            // 아래 
            dp[i][j] = max(dp[i][j], 
                           dp[i - 1][j] - (apple[i][j] - apple[i][j - 1] - apple[i - 1][j] + apple[i - 1][j - 1]));
            
            // 대각선 오른쪽 아래
            dp[i][j] = max(dp[i][j],
                           dp[i - 1][j - 1] + apple[R][j] - apple[R][j - 1] - apple[i][j] + apple[i][j - 1]
                           + banana[i - 1][j] - banana[i - 1][j - 1]);
        }
    }
    
    cout << dp[R][C];
    
    return 0;
} 

 

 

참고

hsdevelopment.tistory.com/567