[JAVA] 백준 9465번 : 스티커

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

9465번: 스티커

---

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

public class Main {
    static int N;
    static int[][] sticker, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            N = Integer.parseInt(br.readLine());
            sticker = new int[2][N];
            for (int i = 0; i < 2; i++) {
                sticker[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }
            dp = new int[2][N + 2];
            for (int i = 2; i < N + 2; i++) {
                dp[0][i] = Math.max(dp[1][i - 1], dp[1][i - 2]) + sticker[0][i - 2];
                dp[1][i] = Math.max(dp[0][i - 1], dp[0][i - 2]) + sticker[1][i - 2];
            }
            //끝 2줄 중 최댓값
            sb.append(Math.max(dp[0][N + 1], dp[1][N + 1])).append("\n");
        }
        System.out.println(sb);
    }
}

💡 DP

풀이

점화식 (2 * n 구성인 경우

dp[0][i] = Math.max(dp[1][i-1], dp[1][i-2]) + sticker[0][i]
dp[1][i] = Math.max(dp[0][i-1], dp[0][i-2]) + sticker[1][i]​

• 0번째줄 i번째 스티커를 떼면, 반대편 i-1, i-2번째 누적합 중 최대인 것을 골라야 함
• 왜 반대편 dp[1][i-1], dp[1][i-2] 중 최대인가?
  • 0번째 i번째에 접근할 수 제일 근접한 위치는 (1) [0, i-2] (2) [1, i-1] (3) [1, i-2]
  • 근데 [0, i-2]는 [1, i-1]에 포함될 수 있으므로 → [1, i-1] , [1, i-2] 이 2가지 탐색함