[백준] 9465 스티커 (JAVA)

풀이

이 문제는 쉬운 DP문제에 속하는 듯하다. 결국 못풀었지만... 일단 알고리즘의 기본 베이스는 DP를 통해 앞에 있던 수들중 가장큰 수를 구하는 것이다. 밑에 있는 코드에서 쉽게 알수있겠지만 DP의 점화식은 다음과 같다.

DP[0][j] = MAX(DP[1][j-1] , DP[1][j-2]) + cost[0][j]이다. 나는 처음 이식을 보고 바로 뒤에(j-2)의 같은 행은 왜 비교를 안하는지 궁금했다. 그러나 잠깐 생각해보니 바로 풀렸다. 왜냐면 같은 행의 두번째 뒤까지 비교해서 구한다면(DP[0][j-2])이는 DP[0][j-2]에서 바로 현재 위치로 온다는 것인데 그렇다면 중간에 더하고 올수있는 대각선을 DP[1][j-1] 그냥 뛰어 넘어 버리기 때문에 이는 문제에서 요구하는 최대값이 될수없다. 그러므로 대각선 바로 뒤와 그 뒤까지만 비교해서 큰수와 현재 위치를 더해서 DP에 저장하면된다.

 

풀이의 이해를 도와주었던 블로그를 달아놓겠다.

https://fbtmdwhd33.tistory.com/76

 

import java.io.*;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        int testCase;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), "");
        int n = 0;

        testCase = Integer.parseInt(st.nextToken());

        for (int t = 0; t < testCase; t++) {
            st = new StringTokenizer(br.readLine(), "");
            n = Integer.parseInt(st.nextToken());
            int[][] cost = new int[2][n + 1];
            int[][] dp = new int[2][n + 1];

            for (int p = 0; p < 2; p++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int q = 1; q <= n; q++) {
                    cost[p][q] = Integer.parseInt(st.nextToken());
                }
            }
            dp[0][1] = cost[0][1];
            dp[1][1] = cost[1][1];
           for(int a=2; a<=n; a++){
               dp[0][a] = Math.max(dp[1][a-1], dp[1][a-2]) + cost[0][a];
               dp[1][a] = Math.max(dp[0][a-1], dp[0][a-2]) + cost[1][a];
           }
           bw.write(Math.max(dp[0][n], dp[1][n]) + "\n");
        }
        bw.flush();
        bw.close();
    }
}