[JAVA] # 9465 스티커

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

public class Main {

    static int N;
    static int[][] board;
    static int[][] dp;

    public static int func() {
        dp[1][0] = board[1][0];
        dp[2][0] = board[2][0];
        for(int i = 1; i < N; i++) {
            dp[0][i] = Math.max(dp[1][i - 1], dp[2][i - 1]); // 현재 라인에서 스티커를 안떼는 경우
            dp[1][i] = Math.max(dp[0][i - 1] + board[1][i], dp[2][i - 1] + board[1][i]); // 1행 스티커를 떼는 경우
            dp[2][i] = Math.max(dp[0][i - 1] + board[2][i], dp[1][i - 1] + board[2][i]); // 2행 스티커를 떼는 경우
        }
        int ans = Math.max(dp[0][N - 1], dp[1][N - 1]);
        return Math.max(ans, dp[2][N - 1]); // 현재 라인에서 최댓값 케이스를 리턴.
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            board = new int[3][N];
            dp = new int[3][N];
            for(int j = 1; j <= 2; j++) {
                stk = new StringTokenizer(br.readLine());
                for(int i = 0; i < N; i++) {
                    board[j][i] = Integer.parseInt(stk.nextToken());
                }
            }
            System.out.println(func());
        }
    }
}

DP로 풀었다..!

 

처음에는 백트래킹 같은 방식을 이용해서 모든 케이스를 하나하나 대조하는게 맞지 않을까 싶었는데, 그러면 너무 복잡해질 것 같아서 dp로 풀려고 했고 결국 푸는데 성공했다!

 

dp[1][0] 는 1열 라인에서 스티커를 떼지 않는 경우의 현재 최댓값을 나타낸다.

1열에서 스티커를 떼지 않는 경우, 0열에서는 스티커를 반드시 떼야 손해보는 것 없이 최댓값을 구할 수 있다.

따라서 앞열에서 1행 스티커를 떼는 경우, 2행 스티커를 떼는 경우 중 더 큰 값을 가지고 있는 걸 선택하면 된다

 

dp[1][1] 는 1열 라인에서 1행 스티커를 떼는 경우의 최댓값

dp[1][2] 는 1열 라인에서 2행 스티커를 떼는 경우의 최댓값을 나타낸다.

 

1열에서 1행 스티커를 떼는 경우는 0열에서 2행 스티커를 뗀 경우 / 0열에서 스티커를 떼지 않은 경우. 두 경우 중 더 큰값을 선택하는 것이 현재에서 최댓값을 구하는 방법이고, dp[1][2] 또한 같다.

 

이걸 N열까지 반복하면 된다!

 

 

그리고 또 조금 헷갈렸던 부분은 배열의 좌표축이다

dp = new int[N][3] 이 아니고 dp = new int[3][N] 이다...