[백준/2281] 데스노트(1차원 dp)

1. 문제

1) 문제 링크

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

2281번: 데스노트

 

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 문제였다!