금고 테스트 (feat. 백준, 2266번)

금고 테스트
https://www.acmicpc.net/problem/2266

2266번: 금고 테스트

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int main()
{
	int N, K, dp[501][501];
	cin >> N >> K;
	for (register int k = 1, n, nn; k <= K; ++k)
		for (n = 1; n <= N; ++n) {
			if (k == 1) {
				dp[k][n] = n;
				continue;
			}
			if (n < k) {
				dp[k][n] = dp[k - 1][n];
				continue;
			}
			dp[k][n] = 99999999;
			for (nn = 1; nn <= n; ++nn)
				dp[k][n] = min(dp[k][n], 1 + max(dp[k - 1][nn - 1], dp[k][n - nn]));
		}
	cout << dp[K][N];
	return 0;
}
// *&)*@*