[BaekJoon] 9465번 스티커 (Java) 문제 풀이 [Silver 1]

문제

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

 

어떻게 풀 것인가?

이 문제는 2행 N열의 스티커에서, 변을 공유하지 않는 스티커를 떼어 최대 점수를 만드는 경우의 수를 구하는 전형적인 2차원 DP(다이나믹 프로그래밍) 문제입니다.

문제 핵심 정리

• 스티커를 하나 떼면, 상하좌우(변을 공유하는) 스티커를 모두 사용할 수 없게 됨
• 2행 N열의 배열이 주어짐
  → 각 스티커에는 점수가 있음
  → 서로 변을 공유하지 않게 떼었을 때 점수 합의 최대값을 구하라

1. 점화식 설계

• dp[0][i] : i번째 열의 윗줄 스티커까지 봤을 때, 이 칸을 선택한 경우 최대 점수
• dp[1][i] : i번째 열의 아랫줄 스티커까지 봤을 때, 이 칸을 선택한 경우 최대 점수

점화식

• dp[0][i] = max(dp[1][i-1], dp[1][i-2]) + arr[0][i]
• dp[1][i] = max(dp[0][i-1], dp[0][i-2]) + arr[1][i]

즉,

• i번째 열의 윗줄을 선택하려면 (직전 아랫줄 or 전전 아랫줄)에서 뽑은 최댓값 + 현재 스티커 점수
• 마찬가지로 아랫줄도 (직전 윗줄 or 전전 윗줄)에서 뽑은 최댓값 + 현재 스티커 점수

2. 초기 조건

• 첫 번째 열:
  dp[0][1] = arr[0][1]
  dp[1][1] = arr[1][1]

 

내 코드 

import java.io.*;
import java.util.*;

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

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

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

            sb.append(Math.max(dp[0][n], dp[1][n])).append("\n");
        }

        System.out.println(sb);
    }
}