[Algorithm]Baekjoon 11058번 :: 크리보드

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

11058번: 크리보드

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
long long dp[101] = { 0 };
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 1; i <= 6; ++i)
    {
        dp[i] = i;
    }
 
    for (int i = 7; i <= n; ++i)
    {
        for (int j = 1; j < 4; ++j)
        {
            dp[i] = max(dp[i], dp[i - 2 - j] * (j + 1));
        }
    }
 
    cout << dp[n];
}

 

 

생각치도 못한 점화식으로 풀리는 문제.. 꽤나 고민했었지만 풀지는 못했다.

살짝 접해보지 못했던 접근이라 그랬던 것 같다.

 

이 문제에서 카운트 1을 소모해서 A를 더하는건, 극초반숫자 (6정도까지?) 까지 말고는 쓸일이없다.

숫자가 조금이라도 커진 순간, 배수로 증가하는 복붙이 무조건 이득이기 때문이다.

기본적으로 버퍼가 비어있을 때, 첫 복붙을 하려면 3의 카운트를 소모해야한다.

 

예를들어 현재 스크린에 A가 5개가 있다면, 3의 카운팅으로 10개가 될 수 있다. 

그리고 버퍼에는 5개가 들어있으니, 이후에는 한번의 카운팅만으로 5개를 스크린에 붙여넣을 수 있다는 것이다.

결국 카운트3소모 완전복붙(컨A+컨C+컨V)와 그냥 컨V를 어느타이밍에 몇번해주느냐가 관건인데, 일정한 규칙이 있는게 아니기 때문에 그냥 i-3,i-4,i-5 번째에 그만큼의 카운팅을 덜소모한만큼 곱한 값 중 제일 큰값으로 dp테이블을 업데이트 하는 것이다.

 

즉, dp[7]기준으로는

 

dp[4] * 2

dp[3] * 3

dp[2] * 4

 

이 세 값중 가장 큰값을 dp[7]값으로 삼는것이다.  복붙에는 최소 3개의 카운팅이 필요하니 i-3부터 하는것이다.

i-3,i-4,i-5만 해도되는 이유는 i-6부터는 값이 너무 작은거에다가 곱하는거라서 이득인경우가 값의 후보가 될수있는 경우가 존재하지 않기 때문이다.