백준 11058 / 크리보드

d[n]을 n번 눌러서 출력할 수 있는 A의 최대 개수라고 하자.

마지막 입력 그러니까 n-1에서 n으로 넘어가는 입력에 따라 경우를 나누어보자.

1. 마지막에 1를 눌렀을 경우

d[n-1]에서 A가 하나 추가되니 d[n]은 d[n-1]+1이다.

2. 마지막에 2를 눌렀을 경우

마지막에 2를 누르는 경우는 최대값이 될 수가 없음으로 무시

3. 마지막에 3을 눌렀을 경우

마지막에 3을 누르는 경우 또한 최대값이 절대 될 수가 없음으로 무시

4. 마지막에 4를 눌렀을 경우

n이 7이상인 모든 경우엔 마지막에 4를 누르고 끝나야 최대값이다.

4를 눌렀다는 것은 2와 3을 이전에 수행했다는 뜻. 

고로 n-3때 2를 누르고 n-2때 3, n-1에 4를 누르는 경우이다.

그러므로 d[n] = 2*d[n-3]

그러나 4를 연속해서 누르는 경우도 있을 것이다.

n-4때의 상황을 복사해서 n-2때 4, n-1때도 4를 누른다면

d[n] = 3*d[n-4]

이것을 점화식으로 표현한다면 

d[n] = (j+1) * d[n-(j+2)]

고로 7부터 입력된 수까지 최대값을 구하면 된다.   왜 7부터냐면 , d[1] ~ d[6]은 1~6이 최대이기 때문이다. (1만 누름)

코드

#include<stdio.h>
#include<iostream>
#include<algorithm>
 
using namespace std;
 
int n;
long long d[101];
 
int main() {
    cin >> n;
 
    d[1] = 1;
    d[2] = 2;
    d[3] = 3;
    d[4] = 4;
    d[5] = 5;
    d[6] = 6;
 
    for (int i = 7; i <= 100; i++) {
        for (int j = 1; j <= i-3; j++) {
 
            d[i] = max(max(d[i - 1] + 1, (d[i - (j+2)] * (j + 1))), d[i]);
        }
    }
 
    cout << d[n];
 
}

P.S

다이나믹 프로그래밍 문제는 진짜 넘 어렵당..

문제를 읽자마자 생각난 로직으로 프로그래밍을 시작하는 것보다 

문제를 차근차근 곱씹어보고 경우도 나누어보고 규칙도 찾아본다음 코드를 짜는게 효율적일 것 같다.

그러므로 DP는 단순히 코딩을 잘한다고 해서 해결할 수 있는 문제가 아니라

문제를 읽어내는 눈이 필요시되는 것 같다.

한마디로 졸라 어렵다는 뜻이다.