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

문제

백준 11058 크리보드 C++

11058번: 크리보드

풀이

DP 문제인데 점화식을 떠올리기가 어려웠다.

처음에 방문체크를 해주는 BFS로 풀려고 했지만... 경우가 많아도 너무 많아서 포기

dp[i]의 최댓값은 다음 중 하나이다.

1. dp[i-1] + 1

2. Ctrl + A, Ctrl + C의 2단계를 거쳐 복사, Ctrl + V로 한 번 붙여넣기한 dp[i-3] * 2

3. 위의 단계를 거쳐 복사, Ctrl + V, Ctrl + V로 두 번 붙여넣기한 dp[i - 4] * 3

4. 위의 단계를 거쳐 복사, 세 번 붙여넣기한 dp[i - 5] * 4

네 번 붙여넣기부터는 다시 복사, 붙여넣기 하는게 더 크다. 따라서 세 번 붙여넣기 까지만 고려해주면 된다.

(출처 : https://blog.naver.com/mym0404/222323009491)

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
long long dp[101];
 
int main() {
    int N;
    cin >> N;
 
    for (int i = 1; i <= 5; i++) {
        dp[i] = i;
    }
    for (int i = 6; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;
        for (int j = 1; j < 4; j++) {
            dp[i] = max(dp[i], dp[i - 2 - j] * (j + 1));
        }
    }
    cout << dp[N];
    return 0;
}