<DP> BOJ 5721 사탕 줍기 대회

문제

문제는 요약하기가 쉽지 않아 링크 참고 바랍니다.

접근

1. 정말 놀라운 사실은 바로 행과 열이 서로 영향을 미치지 않는다는 겁니다. 이게 어떤 말인지 알기 위해 이런 생각을 해봅니다. 1차원 배열이 있다고 생각하고 사탕 줍기 대회의 규칙과 비슷하게 사탕을 주으면 양 옆에 사탕이 없어진다고 생각해봅니다. 이런 상황에서 최대의 결과를 얻기 위해서 어떻게 하면 될까요?
2. $d[N]$을 N번째 index까지 최대 결과라고 정의합니다.
3. 그렇다면 현재 N번째 index의 사탕을 주을지 안주을지 두가지 경우로 나누어 점화식을 세울 수 있습니다.
   $d[N] = MAX(d[N-2]+a[N], d[N-1])$
4. 여기서부터 생각을 좀 더 확장해 문제에 적용해봅니다. 각 행에 대해 3번과 같은 과정을 통해 해당 행에서 구할 수 있는 최대 사탕값을 구합니다. 그럼 우리는 각 행에서 구할 수 있는 최대값을 얻습니다.
   
5. 위와 같은 결과를 얻게 되면 우리는 다시한번 비슷한 과정을 반복하는 점화식을 세울 수 있습니다. 행마다의 최대값과 구분되게 d대신 e를 사용하겠습니다.
   $e[N] = MAX(e[N-2]+e[N], e[N-1])$

코드

import java.io.*;
import java.util.*;

class baek__5721 {
    static int[][] map;
    static int[][] d;
    static int[][] d2;

    static int go(int n, int m) {// 열에서 큰거
        if (m < 0)
            return 0;

        if (d[n][m] != -1)
            return d[n][m];

        d[n][m] = Math.max(go(n, m - 2) + map[n][m], go(n, m - 1));

        return d[n][m];
    }

    static int go2(int n, int m) {
        if (n < 0)
            return 0;

        if (d2[n][m] != -1)
            return d2[n][m];

        d2[n][m] = Math.max(go2(n - 2, m) + go(n, m), go2(n - 1, m));

        return d2[n][m];
    }

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

        StringBuilder sb = new StringBuilder();
        while (true) {
            String[] temp = br.readLine().split(" ");
            int r = Integer.parseInt(temp[0]);
            int c = Integer.parseInt(temp[1]);
            if (r == 0 && c == 0)
                break;

            map = new int[r][c];
            d = new int[r][c];
            d2 = new int[r][c];

            for (int i = 0; i < r; i++) {
                temp = br.readLine().split(" ");
                for (int j = 0; j < c; j++) {
                    map[i][j] = Integer.parseInt(temp[j]);
                    d[i][j] = -1;
                    d2[i][j] = -1;
                }
            }

            sb.append(go2(r - 1, c - 1) + "\n");
        }
        System.out.print(sb);
    }
}