[PS] 백준 9456번 스티커 - DP

문제

예제

풀이

이 풀이를 참고하였다.

스티커의 점수를 저장할 배열 arr[n+1][2]을 선언하고, 점수 합산결과를 저장할 dp[n+1][2] 배열을 선언한다.

첫번째 칸의 점수는 arr배열에서 dp배열로 dp[1][0], dp[1][1] 미리 저장해두고,
두번째 칸 부터 n번째 칸까지 i로 반복문을 돈다. i번째 칸의 점수를 마지막 값이라고 가정하면 최대값이 되기 위해서는 다음 그림과 같이 왼쪽 대각선 칸과 그 옆칸 중 합산값이 큰 값을 골라야 한다.

따라서 dp[i][0]이 마지막 값일 때에는 자신의 값 + dp[i-1][1]과 dp[i-2][1] 중 큰 값이 최대값이 된다.
dp[i][1]이 마지막 값일 때는 자신의 값 + dp[i-1][0]과 dp[i-2][0] 중 큰 값이 최대값이 된다.

d[2][0] = max(dp[1][1]30 / dp[0][1]X) + arr[[2][0]50 -> dp[2][0]의 합산값은 100
d[2][1] = max(dp[1][0]50 / dp[0][0]X) + arr[[2][1]10 -> dp[2][1]의 합산값은 40

d[3][0] = max(dp[2][1]40 / dp[1][1]30) + arr[[3][0]100 -> dp[3][0]의 합산값은 140
d[3][1] = max(dp[2][0]100 / dp[1][0]50) + arr[[3][1]70 -> dp[3][1]의 합산값은 170

...

루프를 다 돌고 나서 첫째 줄과 둘째 줄 중 합산 값이 큰 것이 최대값이다.

코드

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

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(in.readLine());

        int[][] arr;
        int[][] dp;
        String[] str;

        for(int t=0; t<T; t++) {
            int n = Integer.parseInt(in.readLine());

            arr = new int[n+1][2];
            dp= new int[n+1][2];

            for(int i=0; i<2; i++) {
                str = in.readLine().split(" ");
                for(int j=1; j<=n; j++) {
                    arr[j][i] = Integer.parseInt(str[j-1]);
                } //두 줄 읽어들이면서 배열에 저장
            }

            //첫번째 칸 저장
            dp[1][0] = arr[1][0];
            dp[1][1] = arr[1][1];

            //2번째~n번째 칸까지 왼쪽대각선 두개 중 큰값 합산
            for(int i=2; i<=n; i++) {
                dp[i][0] = Math.max(dp[i-1][1],dp[i-2][1]) + arr[i][0];
                dp[i][1] = Math.max(dp[i-1][0], dp[i-2][0]) + arr[i][1];
            }

            //첫째줄과 둘째줄 중 합산값이 큰 것이 최대값
            System.out.println(Math.max(dp[n][0], dp[n][1]));
        }
    }
}