(dp)1463 1로 만들기/9095 1,2,3 더하기

1.1463 1로 만들기

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

1463번: 1로 만들기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int d[1000001];



int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);
    int N;
    cin >> N;

    d[1] = 0;
    for (int i = 2; i <= N; i++) {
        d[i] = d[i - 1] + 1;
        
        if (i % 2 == 0) d[i]=min(d[i / 2] + 1, d[i]);
        if (i % 3 == 0)d[i]=min(d[i / 3] + 1, d[i]);

    }
    cout << d[N];
    return 0;

}

 

2.9095 1,2,3 더하기

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

9095번: 1, 2, 3 더하기

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int d[11];



int main() {
    cin.tie(NULL);
    cin.sync_with_stdio(false);
    cout.tie(NULL);
    d[1] = 1;
    d[2] = 2;                 
    d[3] = 4;

    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int n;
        cin >> n;

        for (int s = 1; s <= n; s++) {
            if (s == 1 || s == 2 || s == 3)
                continue;
            d[s] = d[s - 1] + d[s - 2] + d[s - 3];
        }
        cout << d[n]<<"\n";
    }

    return 0;

}