백준 5721 (사탕 줍기 대회) - java

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

 

문제

상근이는 사탕에 중독된 아이이다. 상근이는 캔디 매거진의 열렬한 구독자이며, 올해 열리는 국제 사탕 줍기 대회에 한국 대표로 참가하게 되었다.

이 대회는 사탕을 포함하고 있는 박스가 M행 N열로 놓여져있는 곳에서 진행된다. (따라서 박스는 총 M × N개 있다) 각 박스에는 들어있는 사탕의 개수가 겉에 적혀져 있다.

대회의 참가자는 박스를 하나 고른다. 그 다음, 그 박스 안에 있는 사탕을 모두 가져가게 된다. 박스를 고르면, 고른 박스의 바로 위쪽 행과 바로 아래쪽 행에 있는 모든 박스, 그리고 고른 박스의 왼쪽과 오른쪽에 있는 박스에 들어있는 사탕이 모두 사라지게 된다. 참가자는 사탕이 들어있는 박스가 없을 때까지 박스를 고를 수 있다.

아래 그림을 살펴보자. 각 칸은 박스에 들어있는 사탕의 개수를 나타낸다. 각각의 단계에서 참가자가 고른 박스는 동그라미로 표시되어 있고, 회색으로 칠해진 박스는 참가자의 선택 때문에 사탕이 사라질 박스이다. 총 여덟 단계가 지나면 게임은 끝나게 되고, 상근이는 총 10+9+8+3+7+6+10+1 = 54개의 사탕을 가져가게 된다.

M과 N이 주어졌을 때, 상근이가 이 대회에서 가져갈 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

 

유형 : DP

 

접근 방식

• 행 단위의 최댓값을 구하여 DP 배열을 만들면 된다.
• 각 행에서 수를 선택할 때의 최댓값을 구한다. (dpRow[i] = max(dpRow[i-1], dpRow[i-2] + v[i])
• 행 단위의 DP 배열을 계산한다. (dp[i] = max(dp[i-1],dp[i-2] + dpRow[i])

 

코드

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

public class BOJ_5721_사탕_줍기_대회 {

    static int n,m;

    static int[] board;
    static int[] tmp;

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

        StringBuilder sb = new StringBuilder();

        while(true) {
            st = new StringTokenizer(br.readLine(), " ");

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());

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

            board = new int[n + 1];
            tmp = new int[m + 1];

            int[] dp = new int[m + 1];

            for (int i = 1; i <= n; i++) {

                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 1; j <= m; j++) {
                    tmp[j] = Integer.parseInt(st.nextToken());
                }

                dp[1] = tmp[1];

                for (int j = 2; j <= m; j++) {
                    dp[j] = Math.max(dp[j - 1], dp[j - 2] + tmp[j]);
                }

                board[i] = dp[m];
            }

            int[] result = new int[n + 1];

            result[1] = board[1];

            for (int i = 2; i <= n; i++) {
                result[i] = Math.max(result[i - 1], result[i - 2] + board[i]);
            }

            sb.append(result[n]+"\n");
        }

        System.out.print(sb);

        br.close();
    }
}