11058번

11058번 - 크리보드

이 문제에 대한 해결을 못봐서 다른 분들의 코드를 봤다.

내가 생각하기에 가장 핵심은, 

점화식 D[n] = n번 눌렀을 때, 출력되는 최대값 이라고 했을 때,

D[1]=1,D[2]=2,...D[6]=6 이라는 점을 알아차리는 것이다. 이 점을 알아차린다는 것은 결국

N이 7이상일 때 2,3,4 번만을 작동해야 한다는 것을 깨닫는 것과 같다.

따라서 기저 조건으로 N이 1~6까지만 알아낸다면 그 다음은 쉽게 풀 수 있다.

N자리 일때, 맨 마지막이 ACV 인 경우, ACVV인 경우, ACVVV인 경우로 나누면 된다.

ACVVVV 는 결국 ACVACV 보다 작게 되기 때문에 3가지 경우만으로 계산을 수행하면 된다.

따라서 

1. ACV 인 경우, D[N-3]의 2배 값을 갖게 된다.(V가 1번이므로 V 1번 + D[N-3] )

2. ACVV인 경우, D[N-4]의 3배 값을 갖게 된다.(V가 2번이므로 V 2번 + D[N-4])

3. ACVVV인 경우, D[N-5]의 4배 값을 갖게 된다.(V가 3번이므로 V 3번 + D[N-5])

위의 세가지 경우의 수 중에서 최대값을 골라내면 된다.

<정답 코드>

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
long long D[101];
long long go(int p)
{
    if (p <= 0)
    {
        return 0;
    }
 
    if (p <= 6)
    {
        return p;
    }
 
    if (D[p] >= 0)
    {
        return D[p];
    }
 
    D[p] = 0;
 
    D[p] = max({ D[p], go(p - 3) * 2, go(p - 4) * 3, go(p - 5) * 4 });
 
    return D[p];
}
int main()
{
    cin >> n;
    memset(D, -1, sizeof(D));
    cout << go(n) << "\n";
 
    return 0;
}