(c++)백준 2281번: 데스노트

www.acmicpc.net/problem/2281

2281번: 데스노트

[풀이]

DP로 풀 수 있는 문제였다.

DP[name][len] : 현재 쓰려는 이름의 인덱스, 해당 줄에 지금까지 쓰인 글자 수

다음 줄로 넘어가는 경우와 넘어가지 않고 그 줄에 쓰는 경우를 비교한다.

 

#include <iostream>
#include <cstring>//memset
#include <algorithm>//min
using namespace std;

int n, m;
int Name[1001];
int dp[1001][1001];

int DP(int name, int len) {//len은 뒤의 빈칸 포함한 길이
	if (name >= n)
		return 0;
	int& res = dp[name][len];
	//이미 구한 값이면
	if (res != -1) {
		return dp[name][len];
	}
	//한 칸 내려서 쓰는 경우
	res = (m - len + 1)*(m - len + 1) + DP(name + 1, Name[name] + 1);
	
	//같은 줄에 쓰는 경우
	if (len + Name[name] <= m)
		res = min(res, DP(name + 1, len + Name[name] + 1));
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> Name[i];
	}
	memset(dp, -1, sizeof(dp));
	cout << DP(0, 0) << '\n';
	return 0;
}