[BOJ 11058] 크리보드

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

해당 문제의 경우 DP로 접근을 한다. 

DP 테이블을 dp[i] = i번째 화면에 출력되는 최대 A의 개수 라고 정의를 한 다음 문제에 접근한다. 

이 문제의 포인트는 

1) i가 7을 넘어가면 버퍼에 있는 것을 복사하는 것이 최대가 된다.

2) 정답은 int의 범위를 넘어간다는 것 (주의)

따라서 버퍼에 들어가기 위해서는 Ctrl +A, Ctrl + C, Ctrl + V 가 필수이므로 버퍼에 들어가는 경우의 점화식은 dp[i] = max(dp[i],dp[i-3]*2) 부터 시작하게 된다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <stdio.h>
#include <cmath>
#define INF 1e9
typedef unsigned long long ull;
 
using namespace std;
 
ull dp[111],n;
 
int main(){
    memset(dp,0,sizeof(dp));
    dp[1] = 1; dp[2] = 2;
    dp[3] = 3; dp[4] = 4;
    dp[5] = 5; dp[6] = 6;
    cin >> n;
 
    for(int i=7;i<=n;i++){
        dp[i] =dp[i-1]+1;
        for(int j=3;j<=6;j++){
            dp[i] = max(dp[i], (dp[i-j]*(j-1)));
        }
    }
    cout << dp[n] <<endl;
    return 0;
}