(백준) 사과와 바나나 _ 3114

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

 

🐢 설명

누적합 문제이다.

 

사과 나라는 트랙터가 지나는 아래쪽의 사과를 얻고 바나나 나라는 트랙터가 지나는 위쪽의 바나나를 얻는다. 이때 트랙터가 지나는 길의 과일은 아무도 얻지 못한다.

 

따라서 트랙터가 지나는 길을 기준으로 사과나라에서 얻을 수 있는 사과 갯수와 바나나 나라에서 얻을 수 있는 바나나 갯수를 별도로 확인해주는 것이 필요하다.

 

예제에서 주어진 2차원 맵을 생각해보자

현재 지도에는 바나나와 사과가 존재하고 트랙터가 어디로 갔냐에 따라 얻을수 있는 사과와 바나나의 개수는 달라진다. 이를 그림으로 나타내보면 아래와 같다.

트랙터가 (0, 0)에 위치한다면 사과 나라는 0열에서 0행을 제외한 아래 1~3행 중 사과 3 + 2개를 얻을 수 있으므로 appleSum[0][0]은 5이다.

appleSum 배열이 의미하는 것은 각 위치에 트랙터가 있을 때 얻을 수 있는 사과의 개수를 의미한다. bananaSum 배열도 동일하다. 특정 좌표에 트랙터가 있다면 사과는 좌표의 아래 부분만, 바나나는 윗 부분만 얻을 수 있다.

 

참고로 bananaSum의 첫 열을 보면 트랙터는 오른쪽 / 대각선 / 아래 로만 이동이 가능하므로 0열에서 0행, 1행, 2행, ... 은 트랙터가 바로 아래로 쭉 이동한 경우에 해당한다. 따라서 바나나는 해당 구간에서 얻을 수가 없다.

 

식으로 나타내보자.

이렇게 각 좌표에 트랙터가 위치할 때 해당 좌표에서 얻을 수 있는 과일의 갯수를 total 배열에 담게 되었다. 이제 이를 이용해서 DP 배열을 완성해보자.

 

DP 배열의 점화식은 두 경우로 볼 수 있다.

• 행이 0인 경우, 그외의 경우

행이 0이라면 왼쪽에서 오른쪽으로 트랙터가 이동한 경우에만 해당한다.

• DP[i][j] = DP[i][j-1] + total[i][j]
• (i, j)에 트랙터가 있다면 왼쪽 DP 값 + 오른쪽 total의 과일개수이다.

행이 0이 아니라면 오른쪽으로 가는 경우, 대각선아래로 가는 경우, 아래로 가능 경우 중에서 최대값을 구한다.

• DP[i][j] = max(  DP[i][j-1] + total[i][j], DP[i-1][j-1] + total[i][j], DP[i-1][j] - apple[i][j]  )
• 오른쪽과 대각선으로 이동하는 경우는 다음 열로 이동하게 되어서 total의 수확량을 더하게 된다.
• 하지만 아래로 이동하는 경우 동일한 열에서 아래 위치로 이동하게 되는 것으로 사과 나라의 사과 수확량이 줄어들게 된다.
• 바나나의 개수는 이미 total값에 포함되어 있으므로 사과 개수만 내려갈 때 마다 빼주면 된다.

이때 DP의 0열은 total의 0열 값으로 세팅하면 된다. 이후 아래로 간다면 사과 개수를 빼주게 될것이고 오른쪽이나 대각선으로 가면 total값을 더하면서 진행이 된다.

🐢코드

package Gold이상문제_정리;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 사과와바나나_3114 {
    static int[][] appleSum = new int[1501][1501];
    static int[][] bananaSum = new int[1501][1501];
    static int[][] apple = new int[1501][1501];
    static int[][] banana = new int[1501][1501];
    static int[][] total = new int[1501][1501];
    static int[][] dp = new int[1501][1501];
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                String s = st.nextToken();
                if (s.charAt(0) == 'A') {
                    apple[i][j] = Integer.parseInt(s.substring(1));
                } else if (s.charAt(0) == 'B') {
                    banana[i][j] = Integer.parseInt(s.substring(1));
                }
            }
        }

        applePrefixSum();
        bananaPrefixSum();
        totalPrefixSum();
        findMaxSum();
        System.out.println(dp[N - 1][M - 1]);
    }

    private static void findMaxSum() {
        for (int i = 0; i < N; i++) {
            dp[i][0] = total[i][0];
        }

        for (int j = 1; j < M; j++) {
            for (int i = 0; i < N; i++) {
                // 0행
                if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + total[i][j];
                } else {
                    dp[i][j] = Math.max(
                            Math.max(
                            dp[i][j - 1] + total[i][j], // 오른쪽
                            dp[i - 1][j - 1] + total[i][j] // 대각선
                            )
                            , dp[i-1][j] - apple[i][j] // 아래
                    );
                }
            }
        }
    }

    private static void totalPrefixSum() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                total[i][j] = appleSum[i][j] + bananaSum[i][j];
            }
        }
    }

    private static void applePrefixSum() {
        for (int j = 0; j < M; j++) {
            for (int i = N - 1; i > 0; i--) {
                appleSum[i - 1][j] = appleSum[i][j] + apple[i][j];
            }
        }
    }

    private static void bananaPrefixSum() {
        for (int j = 1; j < M; j++) {
            for (int i = 0; i < N; i++) {
                bananaSum[i + 1][j] = bananaSum[i][j] + banana[i][j];
            }
        }
    }
}

🐢 마무리