boj 2281 데스노트

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

2281번: 데스노트

노트에 이름을 순서대로 적기 위한 조건은 아래와 같습니다.

1. 위에서 아래로 적습니다.
2. 같은 줄에서는 왼쪽에서 오른쪽으로 적습니다.
3. 이름 사이에는 한 칸의 빈 칸이 있습니다.
4. 한 사람의 이름은 한 줄에만 적어야 하며, 해당 줄에 사람의 이름을 다 적지 못하면 다음 줄에 적어야 합니다.
5. 한 줄을 넘어가는 길이의 이름은 주어지지 않습니다.

위 조건을 지키면서 이름을 적으며, 마지막 줄을 제외한 모든 줄에서 끝에 남은 칸의 갯수의 제곱을 더한 값의 최소를 구하는 문제입니다.

 

dp[idx][len]: idx번째 이름을 적을 차례이고, idx - 1번째까지 len의 공간을 사용했을 때의 최솟값

여기서 선택할 수 있는 방법은

1. 현재 줄을 빈 칸으로 놔두고 다음 줄에 이름을 적는다.
2. 현재 줄에 남은 칸이 이름의 길이만큼 남았다면 현재 줄에 이름을 적는다.

이렇게 두 가지 있습니다.

1번은 모든 경우에 할 수 있으며, 2번은 남은 공간을 파악하여 구하도록 합니다.

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1001
using namespace std;
 
int dp[MAX][MAX], list[MAX];
int N, M;
 
int solve(int idx, int len) {
    if (idx == N) return 0;
 
    int& ret = dp[idx][len];
    if (ret != -1) return ret;
    
    ret = (M - len + 1) * (M - len + 1) + solve(idx + 1, list[idx] + 1);
    if (len + list[idx] <= M) {
        ret = min(ret, solve(idx + 1, len + list[idx] + 1));
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}