[백준 9465 / JAVA] 스티커

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

9465번: 스티커

 

꽤 재밌었던 DP 문제이다.

 

각 스티커를 골랐을 때 가능한 최대값을 구하고 마지막 열의 두 스티커 중 더 큰 값을 출력하면 된다.

쉽게 말해서 스티커를 뗄 때마다 그 상황에서 가장 큰 수를 구하는 것이다.

 

위 사진을 보자 첫번째 열에서 50을 떼어내면 무조건 50이 크고, 30을 떼어내면 30이 크다.

두번째 열에서는 10을 땔 경우 앞에서는 30을 떼어내고, 50을 땔 경우 앞에서는 50을 떼어내야 한다.

여기 까지는 어느정도 정해져 있다.

세번째 열을 보자. 100을 뗄 경우 두 가지 경우가 있다. 앞에서 50과 50을 뗀 경우, 혹은 30을 떼고 두번째 열에서는 아무것도 떼지 않았을 때이다.

70을 뗄 경우도 마찬가지이다. 앞에서 30과 10을 뗀 경우, 혹은 50을 떼고 두번째 열에서는 아무것도 떼지 않았을 경우이다.

 

위와 같은 두가지 경우만 각 상황에 dp를 적용해 해결하면 된다.

 

 

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

public class Main {
    static int T, n;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input;
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());

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

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

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

            for (int j = 2; j <= n; j++) {
                //두 가지 경우 비교
                dp[0][j] += Math.max(dp[1][j - 1], dp[1][j - 2]);
                dp[1][j] += Math.max(dp[0][j - 1], dp[0][j - 2]);
            }

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

        }

    }
}