백준_9465_스티커

스티커

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine()); // 스티커 개수
            int[][] sticker = new int[2][N + 1]; // 스티커 정보 저장 (0: 첫 번째 줄, 1: 두 번째 줄)

            // 스티커 정보 입력
            for (int i = 0; i < 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 1; j <= N; j++) {
                    sticker[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // DP 테이블 초기화
            int[][] dp = new int[2][N + 1];
            dp[0][1] = sticker[0][1];
            dp[1][1] = sticker[1][1];

            // DP 계산
            for (int i = 2; i <= N; i++) {
                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];
            }

            // 최대 점수 출력
            System.out.println(Math.max(dp[0][N], dp[1][N]));
        }
    }
}

DP 배열의 선택 기준

각 위치에서 가능한 선택 : "현재 위치의 대각선에 있는 값"과 "대각선 왼쪽에 있는 값"

1. 대각선 위치 (i-1)

현재 위치의 스티커를 선택하면 바로 위/아래의 스티커는 선택할 수 없기 때문에 대각선 위치에 있는 스티커 값을 참고!

50 10 100 20 40
30 50 70 10 60

예를 들어 dp[0][i]를 계산할 때 dp[1][i-1]를 참고하는 이유는
sticker[1][i-1]은 sticker[0][i]와 인접하지 않기 때문

2. 대각선의 왼쪽 위치 (i-2)

dp[1][i-2] 같은 경우도 인접하지 않은 스티커

50 10 100 20 40
30 50 70 10 60

dp[0][i]를 계산할 때 dp[1][i-2]를 참고하는 이유는 
더 먼 거리에 있는 스티커를 선택함으로써 인접하지 않은 최대 점수를 얻을 수 있기 때문

🤔 왜 같은 줄에서 두 칸 떨어진 위치를 참고 X?

👉 이전에 선택된 스티커와의 인접성
중간에 있는 스티커가 무시될 위험이 있음!

50 10 100 20 40
30 50 70 10 60

sticker[0][2]를 선택하고 sticker[0][4]를 선택하면
중간에 있는 sticker[0][3]을 고려하지 않게 되니까 인접한 스티커들을 제대로 체크하지 못함

즉 선택기준은
👉 대각선에 있는 친구가 선택되었을때 vs 선택 안되었을때!
dp[0][i]를 계산할 때 sticker[1][i-1]가 선택되었을 때와 선택되지 않았을 때의 점수를 비교하는 방식!