1463 1로 만들기

아주 살짝 DP가 어떤 느낌인지 알겠다. 배열만들어서 작은 값부터 채워 넣는 것 같구.. (물론 재귀로 해도 되긴 하지만)

 

값 넣는 건 그리디의 동전 문제 느낌으로 가능한 방법 (3으로 나누기, 2로 나누기, 1 빼기) 중 가장 작은 값 넣으면 된다. 

 

 

 

21일 전에 푼 게 내가 푼 건가?? 기미상궁 하는 다른 팀원인가??

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXN 1e6

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main() {
    int n;
    scanf("%d", &n);

    vector<int> v(MAXN + 10);
    for (int i = 2; i <= n; i++)
    {
        int a = MAXN + 10, b = MAXN + 10, c = MAXN + 10;
        if (i % 3 == 0)
            a = v[i / 3] + 1;
        if (i % 2 == 0)
            b = v[i / 2] + 1;
        c = v[i - 1] + 1;

        v[i] = min({ a, b, c });
    }

    printf("%d\n", v[n]);

    return 0;
}