1463 : 1로만들기

이문제는 정말 경의롭다

1부터 더해나가면 문제를 해결하는데 쉽게 접근 할 수있다.

1은 답이 당연히 1이고.

2는 1에 1을 더한것과 2로나눠지기때문에 2를 나눈 1에 1을 더한것
min(arr[1]+1, arr[2/2]+1)

3은 2에 1을 더한것과 3으로 나눠지기때문에 3을 나눈 1에 1을 더한것

min(arr[2]+1, arr[3/3]+1)

이런식으로 답을 가져가면 N 까지 했을때

arr[N] 에 있는것이 해답이 될것이다.

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

vector<int> DP;

int main(){

    int N;

    cin >> N;

    DP.assign(N+1, 0);

    for (int i = 2; i <= N; i++){

        DP[i] = DP[i - 1] + 1;

        if (i % 2 == 0)DP[i] = min(DP[i], DP[i / 2] + 1);

        if (i % 3 == 0)DP[i] = min(DP[i], DP[i / 3] + 1);

    }

    cout << DP[N] << endl;

    return 0;

}