[BOJ 2281] 데스노트

2281번: 데스노트

1. dp 테이블 정의

dp[x]

👉 arr[x]를 새로운 줄에 적었을 때, 현재의 줄부터 마지막 줄까지의 빈칸 제곱 값

2. 점화식 찾기

빈칸의 수는 1. 해당 줄에 이어서 쓴다 2. 새로운 줄에 쓴다 두가지 선택에 의해 결정된다.

예를 들어,

dp[9]는 arr[9]를 새로운 줄에 적고 arr[10]를 이어적는 경우와 arr[9]를 새로운 줄에 적고 arr[10] 또한 새로운 줄에 적는 경우를 따져볼 수 있다.

dp[8]의 경우는,

1. arr[8]를 새로운 줄에 적고, arr[9] 또한 새로운 줄에 적는 경우
   1. ⇒ 이때, arr[9]를 새로운 줄에 적고 그 이후에 arr[10]을 어떻게 처리할지는 고려할 필요가 없다. dp[9]로 이미 구했기 때문!!
2. arr[8]과 arr[9]를 한 줄에 적고, arr[10]을 새로운 줄에 적는 경우
3. arr[8], arr[9], arr[10]을 모두 한 줄에 적는 경우

를 따져볼 수 있을 것이다.

이를 간단한 코드로 나타내면,

// dp[idx]를 구해보자!
long value = m - arr[idx]; // 값을 채워 넣을 수 있는 남은 빈칸 수
long temp = value * value + dp[idx + 1]; // 해당 줄에 arr[idx]만 넣는 경우!

// 어디까지 더할 수 있는지
for (int i = idx + 1; i < n; i++) { // 현재값의 다음값들을 하나씩 포함시켜 본다!
    if (value - arr[i] - 1 < 0) break; // 해당값부터는 현재 줄에 포함시킬 수 없음.

    if (i == n - 1) { // 이때 포함 시키는 값에 n - 1(마지막 값)도 있다면 무조건 0으로..!
        temp = 0;
    } else {
        value = value - arr[i] - 1; // arr[i]까지 포함시켰을 때의 빈칸 수
        temp = Math.min(temp, value * value + dp[i + 1]);
    }
}
dp[idx] = temp;

위의 규칙에 따라 계산해 보았다.

3. 초기값

dp[n - 1] = 0 → 마지막 줄은 빈칸 수와 상관없이 무조건 0이기 때문.

코드

package DP;

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

// 백준 2281번: 데스노트
public class 데스노트 {

    static int n, m; // n: 사람 수, m: 노트의 가로 길이
    static int[] arr;
    static long[] dp;

    public static long solution(int idx) {
        if (dp[idx] != -1) return dp[idx]; // 이미 dp[idx]를 계산한 적이 있음.

        long value = m - arr[idx]; // 값을 채워 넣을 수 있는 남은 빈칸 수
        long temp = value * value + solution(idx + 1); 
        
        // 어디까지 더할 수 있는지
        for (int i = idx + 1; i < n; i++) {
            if (value - arr[i] - 1 < 0) break; // 해당값부터는 현재 줄에 포함시킬 수 없음.

            if (i == n - 1) { // 이때 포함 시키는 값에 n - 1(마지막 값)도 있다면 무조건 0으로..!
                temp = 0;
            } else {
                value = value - arr[i] - 1;
                temp = Math.min(temp, value * value + solution(i + 1));
            }
        }
        return dp[idx] = temp;
    }

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

        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp = new long[n];
        Arrays.fill(dp, -1);
        dp[n - 1] = 0;

        System.out.println(solution(0));
    }
}