1. 문제
1) 문제 링크
: https://www.acmicpc.net/problem/2281
2281번: 데스노트
첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m
www.acmicpc.net
2) 설명
대강 요약하면 데스노트에 이름을 쓸 때 각 줄별로 뒤의 여백을 구하는 문제다.
각 줄에 이름을 이어서 쓰거나 새로운 줄에 쓸 수 있다. 다만 이름이 중간에 잘리면 그줄에 이어서 못 쓰고 반드시 다음 줄에 새로 써야 한다.
또한 이름 사이에는 한 칸씩 띄어야 한다.
이때 각 줄의 마지막 이름 뒤에 오는 빈 칸들의 제곱의 합을 최소화하는 문제다.
이때 맨 마지막 줄의 빈 칸은 계산할 때 제외한다.
2. 풀이
1) 알고리즘
: DP
2) 풀이 설명
dp 배열에 대한 정의는 다음과 같다.
dp[ i ] : i번째 이름을 새로운 줄에서 시작했을 때, 그 뒤의 이름들로 데스노트를 채워서 얻을 수 있는 빈칸제곱합의 최소값
(말이 좀 어려울 수 있는 것 같다..)
아래 문제의 예시를 살펴보면
n = 11, m = 20
| index | value |
| 0 | 7 |
| 1 | 4 |
| 2 | 2 |
| 3 | 3 |
| 4 | 2 |
| 5 | 5 |
| 6 | 1 |
| 7 | 12 |
| 8 | 7 |
| 9 | 5 |
| 10 | 6 |
dp[10]은 새로운 줄에 index = 10인 이름을 쓰고 (이러면 20 - 6 = 14만큼의 공백이 남는다) 뒤에 더 올 이름이 없으므로 14의 제곱인 196이 된다. 다만 이 경우는 마지막 줄이라 계산하지 않으므로 0이 된다..
dp[9]는 index = 9인 이름을 새 줄에서 시작했을 때의 최소값을 구하면 되는 거다. name[9]는 5글자이므로 뒤에 공백 15칸이 남는다. 그럼 이때 뒤에 남은 name[10]을
1. 이어서 붙여쓸 건지
2. 새 줄에 쓸 건지
에 따라 값이 달라지므로 이 두 가지 경우 중 최소값을 쓰면 된다.
1번처럼 name[10]을 이어서 붙여쓸 경우에는 남은 15칸의 공백 중 띄어쓰기 1칸, 10번째 이름 6칸이 추가로 쓰여지므로 15 - 1 - 6인 8만큼의 공백이 뒤에 남는다. 그러나 이 경우에는 해당 줄이 마지막 줄이 되므로 1의 결과값 후보는 64가 아닌 0이다.
2번처럼 name[10]을 새로운 줄에 쓸 경우에는 남은 15칸의 공백의 제곱인 225에 dp[10]을 더한 225가 결과값 후보가 된다.
결국 dp[9] = min(0, 225) = 0이 된다.
dp[8]도 구해보자.
dp[8]은 index = 8인 이름을 새 줄에 썼을 때의 최소값을 구하면 된다.
그럼 dp[8]은
1. name[9]를 새 줄에 띄어쓰는 경우 -> 결과값 후보 : (20 - 7)^2 + 0( = dp[9]) = 169
2. name[9]를 이어붙이고 name[10]을 새 줄에 쓰는 경우 -> 결과값 후보 : (20 - (7 + 5 + 1))^2 + 0( = dp[10]) = 49
3. name[9], name[10]을 모두 이어붙이는 경우 -> 결과값 후보 : 0
이므로 dp[8] = 0이 된다.
한 번은 0이 아닌 경우를 구해봐야 할 것 같아서 dp[7]이랑 dp[6]까지 값을 구해보면...(이미 이해 됐으면 굳이 안 봐도 될 것 같다...)
dp[7]은
1. name[8]을 새 줄에 띄어쓰는 경우 -> 결과값 후보 : (20 - 12)^2 + dp[8] = 64
2. name[8]은 이어붙이고 name[9] 부터 띄어쓰는 경우 -> 결과값 후보 : (20 - 12 - 1 - 7)^2 + dp[9] = 0
이므로 dp[7] = 0
이때 name[8], name[9]를 이어붙일 수는 없다..! 그러면 한 줄에 20을 넘어가기 때문에..
dp[6]은
1. name[7]을 새 줄에 띄어쓰는 경우 -> 결과값 후보 : (20 - 1)^2 + dp[9] = 361
2. name[7]을 이어붙이고 name[8]부터 새 줄에 쓰는 경우 -> (20 - 1 - 1 - 12)^2 + d[8] = 36
이므로 dp[6] = 36이 된다.
dp[7] 때와 마찬가지로 name[6], name[7], name[8]을 이어붙일 수는 없다. 1 + 1 + 12 + 1 + 7 = 22 > 20이기 때문이다.
이런 식으로 dp배열을 채워나가면 된다.
그렇게 구한 dp[0]은 name[0]을 새 줄에 썼을 때 최소의 결과값을 가지는 거다.
이게 우리가 구하는 값이 된다!(name[0]은 무조건 새 줄의 시작이므로..)
3. 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int N_MAX = 1000;
int n, m;
vector<int> dp(N_MAX, INT_MAX);
vector<int> names(N_MAX, 0);
int solution(int idx){
//계산한 적 있으면 바로 리턴
if(dp[idx] < INT_MAX)
return dp[idx];
int remain = m - names[idx]; //뒤에 다음 이름을 이어붙일 수 있는지 계산하기 위한 변수
for(int i=idx+1;i<=n && remain>=0;i++){
//i번째 이름을 계속 이어붙여가본다. 물론 줄을 넘지 않는 선에서..(remain >= 0)
if(i == n){
//줄을 넘지 않고 모든 이름을 이어붙인 경우다.. 그러면 마지막 줄이라는 말이니까 무조건 dp[idx] = 0이 된다.
dp[idx] = 0;
break;
}
dp[idx] = min(dp[idx], remain * remain + solution(i)); //재귀 호출
remain -= names[i] + 1; //names[i]를 이어붙였으므로 이름 사이의 빈 칸(1) + names[i] 길이만큼을 remain(남은 칸 수)에서 빼준다.
}
return dp[idx];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i=0;i<n;i++)
cin >> names[i];
dp[n - 1] = 0;
cout << solution(0) << endl;
return 0;
}
4. 느낀점
오랜만에 풀어보는 재미있는 dp 문제였다!
'알고리즘 > 백준' 카테고리의 다른 글
| [백준/7512] 연속하는 소수의 합 (0) | 2021.09.20 |
|---|---|
| [백준/1727] 커플 맞추기 (0) | 2021.08.25 |
| [백준/2110] 공유기 설치 (0) | 2021.08.01 |
| [BOJ/1034] 램 (0) | 2021.07.27 |
| [BOJ/7579] 앱 (0) | 2020.12.29 |