(c++)백준 11058번: 크리보드

www.acmicpc.net/problem/11058

11058번: 크리보드

[풀이]

DP를 이용하여 풀 수 있는 문제였다.

DP[i] : i번째 눌렀을 때 A의 최대 개수

점화식

DP[0] ~ DP[5]까지는 A를 하나 출력하는 게 최대

DP[i] = max(DP[i-1]+1,DP[i-3]*2,DP[i-4]*3,DP[i-5]*4)

※화면을 선택하여 복사하는 단계가 있으므로 i-1번째와 i-2번째는 붙여넣을 수 없다.

 

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

int N;
long long dp[101];

void DP() {
	//5번까지는 A를 하나 출력하는게 최대
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	dp[4] = 4;
	dp[5] = 5;
	//A를 하나 출력하는 것과 이전에 복사해둔 것을 붙여넣기 하는 것 비교
	for (int i = 6; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;
		for (int j = 1; j <= i - 2; j++)
			dp[i] = max(dp[i], dp[i - 2 - j] * (j + 1));
	}
	cout << dp[N] << '\n';
}

int main() {
	cin >> N;
	DP();
	return 0;
}