1660_캡틴 이다솜

Concept & Idea

1 3 6 10의 수열을 만들고, 1 4 10 20의 수열을 만드는 것은 쉬운 작업이었다. 처음에는 30만 * 30만은 거뜬할거라 생각했는데, 생각해보니까 시간초과가 날 수 밖에 없었다. 사면체 배열의 수 * 30만 만큼만 비교하면 문제를 더 빠르게 해결할 수 있다.

Code

#include <iostream>
#include <vector>
using namespace std;
int n;
long long layer[200];
vector<long long> vec;
long long dp[300001];
int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        dp[i]=i;
    long long i=1;
    layer[1]=1;
    vec.push_back(layer[1]);
    while(true) {
        layer[i+1]+=i+1+layer[i];
        if(layer[i+1]+vec[i-1]<=n) {
            vec.push_back(layer[i+1]+vec[i-1]);
            dp[vec[vec.size()-1]]=1;
        }
        else
            break;
        i++;
    }
    for(int i=1; i<=n; i++) {
        for(int j=0; j<vec.size(); j++) {
            if(i<vec[j])
                break;
            dp[i]=min(dp[i],dp[i-vec[j]]+1);
        }
    }
    cout<<dp[n]<<endl;
}

 

Fealing

중간에 배열을 벡터로 바꿨더니 런타임에러로 많이 고생하였다. 원래 짜던 스타일과 조금 다르게 짰더니, 코드가 점점 더러워져서 계속 제자리 걸음을 걷다가 정신을 좀 차리고 다시 봤더니 그나마 간결하게 문제를 풀 수 있었다. 인덱스를 좀 더 깔끔하게 사용하도록 하자!