[BOJ] 백준 2281 - 데스노트

문제 링크

www.acmicpc.net/problem/2281

2281번: 데스노트

 

풀이

이름들을 순서대로 그룹 지어준다고 생각해봅시다.

각 그룹 값의 합의 상한은 노트의 폭과 같고, 그룹의 값은 (그룹에 포함된 이름의 길이 합 + [이름 개수] - 1)입니다.

 

간단한 DP로 풀 수 있습니다.

$D[i]$: 그룹이 $i$번 이름으로 시작하고, 그 뒤의 모든 이름을 적절히 그룹으로 묶어주었을 때 남는 칸의 수의 제곱의 합의 최솟값

 

$[i], [i, i+1], [i, i+1, i+2], [i, i+1, i+2, ...]$와 같이 $i$번 이름으로 시작하면서 합이 폭 이하인 그룹의 모든 가능한 경우의 수를 고려하고, 그 뒤의 이름들은 새로운 그룹이 되도록 식을 짜주면 됩니다. 항상 $i$가 그룹의 시작점인 걸로 생각하므로 이전 그룹에 대한 정보가 필요 없으니 일차원 디피 테이블을 잡을 수 있습니다.

 

디테일한 부분은 코드를 참고해주세요.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
using namespace std;

int n, m;
int p[1111], d[1111];

int go(int i) {
    int &ret = d[i];
    if (ret != -1) return ret;

    ret = INF;
    for (int j = i, sum = p[i]; j < n && sum < m + 1; j++, sum += p[j] + 1) {
        if (j == n - 1) {
            ret = 0;
        } else {
            int rest = m - sum;
            ret = min(ret, rest * rest + go(j + 1));
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    memset(d, -1, sizeof(d));
    cout << go(0);
}