[C++] 백준 11058번 크리보드

다이나믹 프로그래밍 문제입니다.

7번까지는 1번(A를 누름)만 누르는 것이 최대입니다.
그 후로는 2가지를 비교합니다.
1.   2, 3, 4(전체 붙여 넣기)
2.   2, 3, 4, 4, 4 ... (복사한것 계속 붙여 넣기)

2번의 경우 계속 붙여넣는것은 3번정도만 비교해주면 충분합니다.
그러면 다음과 같은 4개를 구할 수 있고 이를 비교해서 큰값을 넣어주면 됩니다.

DP[i-1] + 1 (A만 누르는 경우)
DP[i-3] * 2 (3칸전 값 전체 복사 붙여넣기)
DP[i-4] * 3 (4칸전 값 전체 복사 붙여넣기 * 2)
DP[i-5] * 4 (5칸전 값 전체 복사 붙여넣기 * 3)

#include<iostream>
#include<algorithm>
typedef long long ll;

using namespace std;

int main(int argc, char *argv[]) {
	int n;
	int maxNum;
	ll DP[101];

	cin >> n;

	DP[0] = 0;
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 3;
	DP[4] = 4;
	DP[5] = 5;

	for (int i = 6; i <= n; i++) {
		DP[i] = max({ DP[i - 1] + 1, DP[i - 3] * 2, DP[i - 4] * 3, DP[i - 5] * 4 });
	}

	cout << DP[n] << endl;

	return 0;
}