[Java] 백준 스티커

1. 문제분석

문제에서 원하는 것은 스티커를 땠을 때, 때진 스티커의 최대 점수를 말한다.

처음에는 스티커를 때고 남은 것 중 최대 점수를 구하는 줄 알았지만 반대였다.

 

현재 테스트 케이스에서 주어지는 것으로 예를 잡아보자.

먼저 윗줄, 맨 처음 50점을 땠다고 생각하자. 위를 땠을 때 현재 까지의 최고 점수는 50이다.

다음으로 밑줄의 맨 처음, 30점을 땠다고 생각하자. 밑에만 땠을 때 까지 최고 점수는 30이다.

 

다음으로 윗 줄의 두번째 10점을 땐다고 생각하자. 옆의 50과 밑의 50은 때지못한다.(상하좌우가 같이 때지기 때문)

반면 밑의 줄의 30점은 때는 것이 가능하다. 그렇다면 30 + 10으로 40이지만 이미 50이 더 크므로 넘긴다.

이번에는 밑의 줄의 50점을 땐다고 생각해보자. 옆의 30점과 70점은 때지 못한다.

반면 윗 줄의 50점은 가능하다. 그러므로 50 + 50으로 100이 된다. 가장 최고 점수이므로 갱신이 된다.

 

다음 윗 줄의 세번째 100점을 땐다고 생각하자. 왼쪽의 10점과 아래 70점, 오른쪽의 20점은 때지 못한다.

반면 70점 왼쪽의 50점 30점은 가능하다. 하지만 50점을 때면 30점은 못가지게 된다.

그래서 이때 dp값을 불러온다. 내가 30을 땠을 때 최고점과 50을 땠을 때 최고값을 구하면 된다.

그러므로 dp[0][j] = (dp[1][j-1], dp[1][j-2])중 최댓값이다.

 

이번에는 아랫줄로 보자. 아랫줄의 70을 떌려고 한다. 이러면 위의 100점, 왼쪽 50점, 오른쪽 10점은 때지 못한다.

하지만 왼쪽 대각선의 10점, 또는 50점은 가능하다. 마찬가지고 10점을 땠을 때 최댓값이나 50점을 땠을 때 최댓값을 구하면 된다.

즉 dp[1][j] = (dp[0][j-1],dp[1][j-2])중 최댓값을 가져온다.

 

이렇게 위의 경우와 아래 경우를 구하고 마지막에 최댓값을 출력하면 값이 나오게 된다.

 

2. 구현

import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int totalTestCase = Integer.parseInt(br.readLine());
        for (int i = 0; i < totalTestCase; i++) {
            int arrSize = Integer.parseInt(br.readLine());
            int[][] arr = new int[2][arrSize + 1];
            int[][] dp = new int[2][arrSize+1];
            // 데이터 추가
            for(int j = 0; j<2; j++){
                String[] input = br.readLine().split(" ");
                for(int k = 1; k<arrSize+1; k++){
                    arr[j][k] = Integer.parseInt(input[k-1]);
                }
            }
            //dp 초기값 생성 -> dp의 0은 0이다. 0번째를 뽑는데 왜 값이 있겠어?
            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];
            for(int j = 2; j<arrSize+1; j++){
                //위에를 해야할까? 아래를 해야할까?
                dp[0][j] = Math.max(dp[1][j-1],dp[1][j-2]) + arr[0][j];
                dp[1][j] = Math.max(dp[0][j-1],dp[0][j-2]) + arr[1][j];
                //2개중 가장 큰 값으로 설정
            }
            System.out.println(Math.max(dp[0][arrSize],dp[1][arrSize]));
        }
    }
}

항상 헷갈리지만 dp[0], 즉 아무것도 안뽑았을 때는 0이 나오는 것이다.(스티커 조건이 0보다 큼)

그러므로 dp[0][0], dp[1][0]은 0이 된다.(자바는 초기화 안하면 0)

또한 dp[0][1], dp[1][1]은 첫번째 찢었을 경우의 최대값 이므로 arr[0][1], arr[1][1]값과 동일하다.

 

3. 마무리

DP의 점화식을 제대로 구했다! 싶어도 항상틀리는 것 같다.

모든 경우의 수를 종합하고 점화식을 구해야겠다.

그래도 점화식을 세울려고 했으니 조금은 늘었다는 생각이 들었다.