[백준] 2281 - 데스노트

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

2281번: 데스노트

 

처음에 이분 탐색으로 해결하려고 했다가, 이분 탐색의 조건에 맞지 않아서 실패했고, 다음으로 다이나믹 프로그래밍으로 시도했다.

dp로 풀기 위해서 배열을 다음과 같이 정의했다.

dp[i] = i번째 사람의 이름까지 적었을 때, 제곱의 합의 최소

 

이렇게 되면 점화식은 굉장히 간단해진다. i 이전에 모든 경우의 수를 찾아서, 어디서 줄을 바꿀 건지만 결정하면 된다.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        if (sum[i] - sum[j - 1] + i - j > m) {
            continue;
        }
        int c = dp[j - 1] + (m - (sum[i] - sum[j - 1] + i - j)) * (m - (sum[i] - sum[j - 1] + i - j));
        if (dp[i] == -1 || dp[i] > c) {
            dp[i] = c;
        }
    }
}

 

그런데 답을 구하는 과정에서, 제일 마지막 줄은 계산하지 않는다라고 한다.

이 부분을 위해서 한 번만 배열을 더 훑어서 마지막 줄이 가능한 위치에서의 최솟값을 구하면 된다.

 

#include <iostream>
#include <cstring>
using namespace std;

int n, m, a[1001], sum[1001], dp[1001];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    dp[1] = (m - a[1]) * (m - a[1]);
    int ans = 2000000000;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (sum[i] - sum[j - 1] + i - j > m) {
                continue;
            }
            int c = dp[j - 1] + (m - (sum[i] - sum[j - 1] + i - j)) *
                                    (m - (sum[i] - sum[j - 1] + i - j));
            if (dp[i] == -1 || dp[i] > c) {
                dp[i] = c;
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        if (sum[n] - sum[i] + n - i <= m) {
            ans = min(ans, dp[i]);
        }
    }
    cout << ans;
}