https://www.acmicpc.net/problem/2281
2281번: 데스노트
첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m
www.acmicpc.net
노트에 이름을 순서대로 적기 위한 조건은 아래와 같습니다.
- 위에서 아래로 적습니다.
- 같은 줄에서는 왼쪽에서 오른쪽으로 적습니다.
- 이름 사이에는 한 칸의 빈 칸이 있습니다.
- 한 사람의 이름은 한 줄에만 적어야 하며, 해당 줄에 사람의 이름을 다 적지 못하면 다음 줄에 적어야 합니다.
- 한 줄을 넘어가는 길이의 이름은 주어지지 않습니다.
위 조건을 지키면서 이름을 적으며, 마지막 줄을 제외한 모든 줄에서 끝에 남은 칸의 갯수의 제곱을 더한 값의 최소를 구하는 문제입니다.
dp[idx][len]: idx번째 이름을 적을 차례이고, idx - 1번째까지 len의 공간을 사용했을 때의 최솟값
여기서 선택할 수 있는 방법은
- 현재 줄을 빈 칸으로 놔두고 다음 줄에 이름을 적는다.
- 현재 줄에 남은 칸이 이름의 길이만큼 남았다면 현재 줄에 이름을 적는다.
이렇게 두 가지 있습니다.
1번은 모든 경우에 할 수 있으며, 2번은 남은 공간을 파악하여 구하도록 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#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;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 14450 Hoof, Paper, Scissors (Gold) (0) | 2022.12.30 |
|---|---|
| boj 14453 Hoof, Paper, Scissors (Silver) (0) | 2022.12.30 |
| boj 2015 수들의 합 4 (0) | 2022.08.12 |
| boj 21923 곡예 비행 (0) | 2022.06.10 |
| boj 12978 스크루지 민호 2 (0) | 2022.06.08 |