사용한 알고리즘
알고리즘 설명
- 일반적인 DP 문제이다
- N이 최대 100인 작은값을 가진다
- 이러한 점에서 O(N^2) 형태의 알고리즘을 사용한다
- dp 점화식을 세운다
- dp는 1차원으로 state를 정하고 문제를 푼다
- dp[N]은 N개의 커맨드를 이용하여 가지는 최대 값으로 정의한다
- state 업데이트 방식은 다음과 같다
- dp[N+1] = dp[N] + 1 // 1개의 A를 추가하는 커맨드
- dp[N+1] = dp[N] + step // Ctrl + V를 사용하는 경우
- 우리가 주의깊게 보아야 하는 부분은 Ctrl + V의 경우이다
- step은 dp[N-3]이 가지는 최대 값이 바로 step 사이즈다
- 이러한 점을 이용하여 각 step 에 따라 가지는 모든 값을 구한다.
풀이
// baekjoon 11058 yechan
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX_N=101;
int N;
ll dp[MAX_N];
int main() {
scanf("%d", &N);
dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=4, dp[5]=5;
for (int i=4; i<MAX_N; i++) {
ll step = dp[i-3];
for (int j=0; i+j<MAX_N; j++) {
dp[i+j] = max(dp[i+j], step * (j+2));
}
}
printf("%lld\n", dp[N]);
return 0;
}
