훈감자 블로그

재귀로 dp하니 TLE 나서 for문으로 구현하니 통과..

For문 연습해야겠다..

ㅇ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_ 987654321

typedef long long int INT;
INT n;
int main()
{
    cin >> n;

    vector<INT> v;
    v.resize(n+1);
    v[1] = 0;
    for(INT i=2; i<=n; i++)
    {
        v[i] = MAX_;
        if(i%2==0)
        {
            v[i] = min(v[i], v[i/2]+1);
        }
        if(i%3==0)
        {
            v[i] = min(v[i], v[i/3]+1);
        }
        if(i-1>0)
        {
            v[i] = min(v[i], v[i-1]+1);
        }
    }

    cout << v[n];
}

Dp 구현을 했더니 메모리 초과가 뜸 -> 귀찮아서 그냥 케이스 분류로 풂.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int INT;

INT n,ans;

int main()
{
    cin >> n;

    INT a = (n%5)%3==0?n/5+(n%5)/3:987654321;
    if(a==987654321)
    {
        INT i = n;
        INT d = 5;
        INT chk = 987654321;
        while(i-5>0)
        {
            i-=5;
            
            if(i%3 == 0)
            {
                chk = min(chk,(n-i)/5+i/3);
            }
        }
        if(chk!=987654321)  a = chk;
    }
    INT b = n%5==0?n/5:987654321;
    INT c = n%3==0?n/3:987654321;
    ans = min({a,b,c});
    INT p = ans!=987654321?ans:-1;

    cout << p;

    return 0;
}

정석대로 풀어봐야겠다..

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int INT;
set<INT> chk;

int main()
{
    for(INT i=1; i<10001; i++)
    {
        INT a=i;
        INT b=i;
        while(a/10 != 0)
        {
            b += a%10;
            a /= 10;
        }
        b += a;

        if(b<=10000)    chk.insert(b);
    }

    for(int i=1; i<10001; i++)
    {
        if(!chk.count(i))
        {
            cout << i << endl;
        }
    }

}