[DP] 백준 9466번 스티커 - JAVA

 

역시 dp는 어렵다...

오늘도 어김없이 답을 봤다.

답을 보면 다른 개발자분의 생각을 읽을 수 있다는 점에선 좋지만,

내 스스로 풀이 능력이 떨어지는 것 같아 항상 블로그에 글을 남긴다 ㅠ

 

---

1. 출처

---

 

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

9465번: 스티커

 

• 각 스티커에는 점수가 붙어있다.
• 하나의 스티커를 뜯으면 4방에 인접해있는 스티커는 못쓴다.
• 최대 점수가 될 수 있게 스티커를 뜯자!

 

---

2. 설계

---

 

 

1. 오답 설계 - 그리디

사실 처음에는 난이도가 실버이기도 하고, 쉽게 보여서 그리디 문제인 줄 알았다. 그래서 스티커 점수를 가장 큰 것부터 내림차순 정렬해서 뜯었는데 이게 웬걸?! 1%에서 틀렸다 ㅎㅎ 알고보니 DP 문제였던 것이다. 어찌 이 문제를 보고 바로 DP를 생각할 수 있는거지?...

 

 

2. 정답 설계 - DP

DP라고 하면 작은 문제를 해결해 큰 문제를 해결할 수 있는 문제이다. 그러기 때문에 작은 문제를 해결할 수 있는 공식이 있을 것이다. 사실 나는 잘 생각이 나지 않아서 풀이를 참고했다. 결론부터 말하자면 다음과 같다.

 

• [0][c] 위치이면, [1][c-1] 위치와 [1][c-2] 위치에 있는 것 중 가장 큰 점수와 나를 더해 dp에 저장한다.
• [0][1]  위치이면, [0][c-1] 위치와 [0][c-2] 위치에 있는 것 중 가장 큰 점수와 나를 더해 dp에 저장한다.

 

왜??? 이 문제에서 dp 테이블은 어떠한 의미일까?

dp 테이블은 각 스티커를 떼었을 때 얻을 수 있는 가장 큰 점수다.

 

만약 (0,3)에 스티커를 뜯는다고 가정하면, 가장 많은 점수를 얻기 위해 즉, 최대한 많은 스티커를 뜯기 위해!

위와 같은  2가지 케이스가 나올 수 있다.

 

 

그런데 1번 케이스의 경우 [1][1]은 [0][0]과 자신을 합한 값을 가지고 있으므로 [0][2]에서는 [0][0]을 고려해주지 않아도 된다.

즉, [1][1]은 [1][1] 스티커를 뜯었을 때 얻을 수 있는 가장 높은 점수를 가지고 있다. ([0][0] + [1][1] = 현 상황에서 최대 점수)

때문에 [0][2]는 [0][2]의 스티커를 뜯었을 때 [1][1]를 뜯을까 [1][0]을 뜯을까만 고민하면 된다.

 

 

예제 1번을 dp로 나타내면 다음과 같다.

 

결과는 [0][N]과 [1][N] 중 가장 큰 것을 정답으로 하면 된다.

주의할 점은 0번 라인 쭉 돌고, 1번 라인 쭉 돌면 안된다는 것이다. 1번라인은 0으로 도배되어 있기 때문이다.

[1][0] -> [1][1] -> [2][0] -> [2][1] 이렇게 차례대로 계산해줘야 다음 dp의 정확한 값을 계산할 수 있다.

 

 

---

3. 전체 코드

---

 

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

//DP

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        for(int T=1;T<=t;T++){
            int N = Integer.parseInt(br.readLine());
            
            int[][] score = new int[2][N+1];
            for(int i=0;i<2;i++){
                String scores = br.readLine();
                StringTokenizer st = new StringTokenizer(scores, " ");
                for(int j=1;j<=N;j++){
                    score[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int[][] dp = new int[2][N+1];
            dp[0][1] = score[0][1];
            dp[1][1] = score[1][1];

            for(int c=2;c<=N;c++){
                dp[0][c] = Math.max(dp[1][c-1], dp[1][c-2])+score[0][c];
                dp[1][c] = Math.max(dp[0][c-1], dp[0][c-2])+score[1][c];
            }

            System.out.println(Math.max(dp[0][N], dp[1][N]));

        }//for T
    }
}