[BOJ] 5721. 사탕 줍기 대회

문제 원본 : https://www.acmicpc.net/problem/5721

5721번: 사탕 줍기 대회

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st;
        StringBuilder builder = new StringBuilder();
        int m, n;
        int[][] candy;
        int[] rowCandy, rowDp, colDp;

        while (true) {
            st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            if (m == 0 && n == 0) {
                break;
            }

            candy = new int[m][n];
            rowCandy = new int[m];
            rowDp = new int[m];
            colDp = new int[n];

            for (int i = 0; i < m; ++i) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; ++j) {
                    candy[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < m; ++i) {
                colDp[0] = candy[i][0];

                if (n > 1) {
                    colDp[1] = Math.max(candy[i][0], candy[i][1]);
                }

                for (int j = 2; j < n; ++j) {
                    colDp[j] = Math.max(colDp[j - 1], colDp[j - 2] + candy[i][j]);
                }
                rowCandy[i] = colDp[n - 1];
            }

            rowDp[0] = rowCandy[0];

            if (m > 1) {
                rowDp[1] = Math.max(rowCandy[0], rowCandy[1]);
            }

            for (int i = 2; i < m; ++i) {
                rowDp[i] = Math.max(rowDp[i - 1], rowDp[i - 2] + rowCandy[i]);
            }

            builder.append(rowDp[m - 1]).append("\n");
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }
}

• 다이내믹 프로그래밍 문제
• 아이디어 참고
• 기본 점화식은 dp[i] = Max(dp[i - 1], dp[i - 2] + candy[i])
• 각 행마다 최댓값을 구한 뒤, 그 최댓값의 배열을 다시 동일한 점화식으로 풀면 된다.