[백준] 2281번: 데스노트

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

2281번: 데스노트

다이나믹 프로그래밍 문제 접한 지 오래되어서 감 떨어질까봐 접한 문제인데, 눈물 나게 어려웠다..

 

처음에는 일일이 해야하나 싶다가 해당 이름을 현재의 줄에 그대로 쓸지, 아니면 새로운 줄에 쓸지 결정하는 게 이 문제 풀이의 핵심까지는 캐치했다.

 

이 문제는 이전 다이나믹 프로그래밍과 다르게 풀면 쉽게 접근할 수 있다.

이전까지는 주로 앞 내용을 기반으로 앞 내용을 반복적으로 사용하고자 앞에서부터 다이나믹 프로그래밍을 하는 경우가 많았다.

하지만 이번에는 뒷 내용을 반복적으로 사용한다.

 

왜냐하면 처음에는 휴리스틱하게 문제를 풀다보면 자연스럽게, 새로운 줄에 쓸지 말지 결정하다가 결국 특정 이름을 쓰는 순간 새로운 줄이 시작될텐데 그 결과는 이미 이전이나 후에 다시 쓰일 가능성이 있기 때문이다.

 

dp[i] = i번째 이름을 새로운 줄에서 시작했을 때 그 뒤의 이름들로 데스노트를 채워서 얻을 수 있는 빈칸 수 제곱 합의 최솟값

 

처음에는 문제가 어려워서 2차원으로 접근해야하나 싶었지만, 어차피 for문을 이용해 dp 값들을 이용하기 때문에 2차원 배열은 불필요하다.

 

i번째 단어가 새 줄에서 시작한다고 가정하고, 점차 한 단어씩 늘려가면서 빈칸을 줄일 수 있는 데까지 줄여본다.

이러면 특정 단어가 빠져서 빈칸으로 있는 경우는 dp 배열에 없는 거 아니냐구?(이거 때문에 처음에는 2차원 배열을 고려했었음)

아니다. 바로 다음 인덱스에 그 특정 단어로 시작하는 경우가 있기 때문에 for문을 통해 탐색이 가능하다.

 

이번 문제를 통해서 해당 인덱스에 관한 모든 정보가 들어있지 않고 주변 정보를 충분히 활용할 수 있음을 깨달았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int n, m;
vector<int> names(1000);
vector<int> dp(1000, INT_MAX);
int solution(int idx) {
	// 계산한 적 있으면 바로 리턴
	if(dp[idx] < INT_MAX) {
		return dp[idx];
	}
	// 뒤에 다음 이름을 얼마나 이어붙일 수 있을지 알기 위함
	int remain = m - names[idx];
	int next = idx + 1;
	// 첫번째에는 혼자서 새줄에 쓰는 경우
	while(remain >= 0 && next <= n) {
		if(next == n) {
			dp[idx] = 0;
			break;
		}
		// 재귀 호출
		dp[idx] = min(dp[idx], remain * remain + solution(next));
		remain -= names[next] + 1;
		next++;
	}

	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];
	}
	// i번째 이름을 새로운 줄에서 시작했을 때 그 뒤의 이름들로 데스노트를 채워서 얻을 수 있는 빈칸 수 제곱 합의 최솟값
	dp[n - 1] = 0;

	cout << solution(0) << '\n';

	return 0;
}

 

대신 최댓값 설정을 제대로 못해서 시간 초과가 발생했다.ㅠㅠ

반성하자 제발. 문제에 제곱이라고 써있다구,,