1로 만들기 1463

문제

접근 방법

일단 각 단계에 대해서 차례대로 생각해봤다.
1을 뺀다는 건 반대로 1일 때부터 1씩 올리며 X에 도달할 수도 있단 것이다.

1 2 3 4 5 6 값
0 1 2 3 4 5 연산

2로 나누어떨어지는 경우를 생각해보자.

1 2 3 4 5 6 값
0 1 2 2 3 3 연산

[값/2]+1의 형태를 보인다. +1은 2를 곱한 연산이라고 보면 된다.
3으로 나누어 보자.

1 2 3 4 5 6 값
0 1 1 2 3 2 연산

[값/3]+1의 형태를 보인다.
이를 이용하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    vector<int> v(N + 1);
    v[0] = v[1] = 0;
    for (int i = 2; i <= N; ++i)
    {
        if (i % 6 == 0)
            v[i] = min(min(v[i / 3] + 1, v[i / 2] + 1), v[i - 1] + 1);
        else if (i % 3 == 0)
            v[i] = min(v[i / 3] + 1, v[i - 1] + 1);
        else if (i % 2 == 0)
            v[i] = min(v[i / 2] + 1, v[i - 1] + 1);
        else
            v[i] = v[i - 1] + 1;
    }
    cout << v[N];
    return 0;
}

풀이

처음에는 3, 2의 경우만 생각하고 풀었다.
그러자 오답이 떴다.
반례를 찾던 중 642의 경우를 알게 됐다.
2로 나누는 것이 더 나은 경우가 있다는 것이다.

10의 경우도 마찬가지다. 2로 나눠지지만, 앞에 숫자에 +1한 경우가 더 나을 수도 있다. (9는 3으로 나누어지므로)

각각 일어날 수 있는 경우 중 최솟값을 대입해주면서 진행하면 된다.

DP 문제를 많이 풀어봐야겠다.