[CQUOJ 21412] 소프트 코인!부드러운 여동생 코인!부드러운 여동생 코인!(수학+DP)

CQUOJ-21412 문제는 대체로 몇 개의 다른 수 중 몇 개를 더하고 빼면 1...n 사이의 모든 수를 얻을 수 있다. 필요한 최소 몇 개의 다른 수 경기에서 규칙을 찾아 한 것이다. 비록 지났지만 안정감이 없어서 경기 후에 문제를 보고 문득 깨달았다.
우선 이런 사실이 있는데, 만약 세 개의 수가 1을 나타낼 수 있다면...13 그러면 13보다 작은 n에 대한 답은 기껏해야 3이기 때문에 우리는 i개수로 구성할 수 있는 가장 큰 수가 얼마나 되는지 고려할 수 있다
dp[i]를 설정하면 i의 개수가 [1,dp[i]를 나타낼 수 있다. 이때 나는 dp[i]보다 큰 수를 표시하려면 반드시 dp[i]보다 큰 수를 넣어야 한다. x를 설정하면 이때 나는 [x-dp[i], x+dp[i]] 구간의 수를 추가로 표시할 수 있다. 이 구간은 [1,dp[i]와 중합될 수 있다. 오른쪽 단점을 최대화하기 위해 x를 계속 오른쪽으로 이동한다. x-dp[i]=dp[i]+1까지 추가된다. 이때 추가된 구간은 원래 구간에 공공점이 없기 때문에 dpi*1]이 없다.오른쪽 단점은 3*dp[i]+1이기 때문에 x를 넣은 후 i+1개의 수는 [1,3*dp[i]+1] 전이 방정식을 나타낼 수 있다. 1)dp[1]=1;2) dp[i]=dp[i-1]*3+1

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define LL long long
#define ULL unsigned long long
#define Pow2(a) a*a
int maxx(int a,int b){return a>b?a:b;}
int minn(int a,int b){return a<b?a:b;}
int abss(int a){return a<0?(-a):a;}

int N;
int dp[13];

int main()
{
    dp[1]=1;
    for(int i=1; i<13; i++) dp[i]=dp[i-1]*3+1;
    while(~scanf("%d", &N))
    {
        for(int i=1; i<13; i++)
        {
            if(dp[i]>=N)
            {
                printf("%d
", i);
                break;
            }
        }
    }
    return 0;
}