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

https://www.acmicpc.net/problem/11058

11058번: 크리보드

 본 문제는 크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대 개수를 구하는 문제로 문제의 조건은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

이때, 조건 2~4은 연속적으로 일어나야 의미가 있다. 따라서 조건 2~4은 하나의 조건으로 생각하는것이 좋다. 조건 4은 조건 2~3이 선행되었을 때 반복해서 누를수 있다. 즉, i를 버튼을 누른 횟수, j를 조건 4를 실행한 횟수, d[i]를 i번 버튼을 눌러 화면에 출력되는 A의 최대 개수라 하면 다음과 같은 점화식을 정의할 수 있다. d[i] = max(d[i-1] + 1, d[i-j] * (j-1)) (단, 3 ≤ j ≤ i)

#include <cstdio>
 
using namespace std;
 
long long d[101];
 
int Max(int x, int y) {
    if (x < y) return y;
    else return x;
}
 
int main() {
    int n;
    scanf("%d", &n);
    d[0] = 0;
    for (int i = 1; i <= n; i++) {
        d[i] = d[i-1] + 1;
        for (int j = 3; j <= i; j++) {
            if (d[i] < d[i-j]*(j-1)) d[i] = d[i-j]*(j-1);
        }
    }
    printf("%lld\n", d[n]);
}