[JAVA] 백준 9465번- 스티커

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

9465번: 스티커

 

 

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

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

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

        while(T-->0){
            int n = Integer.parseInt(br.readLine());

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

            for(int i=0; i<2; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j=1; j<=n; j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            dp[0][1] = arr[0][1];
            dp[1][1] = arr[1][1];

            for(int i=2; i<=n; i++){
                dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + arr[0][i]; // 왼쪽 아래 대각선
                dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + arr[1][i]; // 왼쪽 위 대각선
            }

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

 

dp[i][j] = (i, j)까지의 스티커를 뽑을 때 최대 점수의 합

 

 

상하좌우 붙어있는 스티커는 뽑을 수 없으므로 대각선으로만 선택이 가능하다.

위에 있는 스티커일 경우 그 전에 선택되어야할 스티커는 한칸 왼쪽 아래 대각선이거나 두칸 왼쪽 아래 대각선에 있어야한다.

아래에 있는 스티커일 경우 그 전 스티커는 한칸 왼쪽 위 대각선이나 두칸 왼쪽 위 대각선에 있어야 한다.

 

여기서 간과해서 헤맸던 점이 있다..

그럼 대각선이 아닌 두칸 앞 스티커는?

 

50	10	100	20	40
30	50	70	10	60

 

 

내가 말한 예는 맨 왼쪽 위 50에서 100으로 바로 가는 경우이다.

이 경우는 50 -> 50 -> 100 으로도 갈 수 있다.

우리가 구하고자 하는것은 합의 최댓값이므로 저렇게 가는 경우는 고려하지 않는다.

50 -> 20, 10, 60, 40 도 마찬가지다. 

 

 

 

그러므로 점화식은 이렇게 세울 수 있다. 

dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + arr[0][i]; 
dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + arr[1][i]; 

 

 

마지막에는 n번째 열의 최댓값을 반환한다.