[백준 9465] 스티커

문제

---

접근

• DP 사용해서 이전의 결과값을 사용해서 효율적인 계산을 진행하였다.
• 예시
  • 스티커를 뗀 부분이 O이고
  • 찢겨진 부분은 X라고 하자.

dp 배열과 스티커 배열의 사이즈

• (0,2) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. 지금 목표는 스티커를 뗀 경우 중 가장 큰 값을 얻었을 때이기 때문에 이때 둘 중에 큰 값을 선택하고 (0,2) 위치의 스티커 값을 더해주면 된다.
  • 이외에 아무것도 떼지 않은 경우
  • (1,1) 위치의 스티커를 뗀 경우

 

• (0,3) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. 
  • (1,2) 위치의 스티커를 뗀 경우
  • (1,1) 위치의 스티커를 뗀 경우
  • 해당 값 중에 큰 값을 선택하고 (0,3) 위치의 스티커 값을 더해주면 된다.

 

그러면 아래와 같은 점화식을 얻을 수 있다.

구한 점화식을 코드에 적용하면 아래 코드와 같다.

---

코드

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

public class Main {
    static int testCase;
    static int N;
    static int[][] sticker;
    static int[][] dp;
    static BufferedReader br;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        testCase = Integer.parseInt(br.readLine());
        StringBuffer sb = new StringBuffer();

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

            for (int j = 2; j <= N; j++) {
                dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + sticker[0][j];
                dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + sticker[1][j];
            }

            int maxScore = Math.max(dp[0][N], dp[1][N]);
            sb.append(maxScore + "\n");
        }
        System.out.println(sb.toString());
    }

    private static void settingScore(int n) throws IOException {
        for (int i = 0; i < 2; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j < n + 1; j++) {
                sticker[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

}