11058 크리보드

1. 문제

2. 코드

#include <queue>
#include <iostream>
 
using namespace std;
 
int N;
long dp[101];
 
long solve(int n);
 
int main()
{
    scanf("%d", &N);
    printf("%ld", solve(N));
}
 
long solve(int n) {
    if (n <= 0)
        return 0;
    if (n == 1)
        return dp[n] = 1;
    if (dp[n] > 0)
        return dp[n];
 
    //A를 입력할 경우
    dp[n] = n;
    dp[n] = max(dp[n], solve(n - 1) + 1);
 
    //복붙할 경우
    int j = 2;
    //5번째전~ 3번째전꺼를 계속 붙여넣기했을 때 값 비교
    for (int i = n - 3; i > n - 6; i--) {
        //A를 입력할 경우와 비교
        dp[n] = max(dp[n], solve(i)*j);
        j++;
    }
    return dp[n];
}
 

3. 후기

이 문제는 단순히 A를 추가하는 것과 복사붙여넣기 하는 것을 비교하는데 몇번째 전꺼를 복사 붙여넣기 하는지가 관건이다. 그래서 N-5일 때 드래그, 복사, 붙여넣기, 붙여넣기, 붙여넣기 이므로 solve(n-5)*2 부터 n-4, n-3까지 다 비교해본다 숫자가 커질수록 더 큰 수를 붙여넣기하지만, 붙여넣기하는 횟수는 적어지기 때문에 비교를 해서 큰 값을 리턴해주어야 한다. 

출처 - https://stack07142.tistory.com/148