[백준 9465번 / Java] 스티커 - DP

문제 링크

Silver 1

 

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

9465번: 스티커

 

 

 

 

 

풀이

문제의 조건은 선택한 스티커의 상하좌우 스티커는 선택할 수 없다. 라고 하였다. 아래 문제 예시를 보자.

50	10	100	20	40
30	50	70	10	60

위의 예시에서, dp를 사용하여 최대값을 어떻게 구할 수 있을까

 

 

왼쪽부터 시작해서, 하나씩 선택해보았다.

50	10
30	50

50	10
30	50

첫 번째 idx의 값을 선택할 수 있다.

두 번째 idx까지는 문제 없이 선택할 수 있다. 자연스럽게 가로, 세로의 값은 선택할 수 없기 때문에

(50,50) = 100 / (30,10) = 40의 결과가 나올 것이다.

 

 

만약 세 번째 idx에서부터는, 이전 값의 최대값을 더한 값을 표현하려면 어떻게 해야 할까?

50	40
30	100

위의 두 번째 idx에는 이미 두 번째 idx까지의 최대값이 담겨있다. 그럼 이전처럼 idx - 1의 값을 더해가면 되는 것일까?

그렇지 않다. 아래의 예시처럼 만약 idx - 2의 값이 더 큰 경우까지 고려해주어야 한다.

50	130
120	100

 

이러한 상황들을 고려한 점화식은 다음과 같다.

dp[0][j] += j == 1 ? dp[1][j - 1] : Math.max(dp[1][j - 2], dp[1][j - 1]);
dp[1][j] += j == 1 ? dp[0][j - 1] : Math.max(dp[0][j - 2], dp[0][j - 1]);

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int N;
    private static int T;

    private static int[][] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        for(int i = 0; i < N; i ++) {
            T = Integer.parseInt(br.readLine());
            dp = new int[2][T];

            for(int j = 0; j < 2; j ++) {
                st = new StringTokenizer(br.readLine(), " ");
                for(int k = 0; k < T; k ++) {
                    dp[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            for(int j = 1; j < T; j ++) {
                dp[0][j] += j == 1 ? dp[1][j - 1] : Math.max(dp[1][j - 2], dp[1][j - 1]);
                dp[1][j] += j == 1 ? dp[0][j - 1] : Math.max(dp[0][j - 2], dp[0][j - 1]);
            }
            System.out.println(Math.max(dp[0][T - 1], dp[1][T - 1]));
        }

    }
}