문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

해설

문제의 규칙을 점화식으로 표현하자면 다음과 같다.
$ \mathrm{D}(i) = \begin{cases} D[i-1]+1 \
min(D[i],D[i/2]) & i\pmod2 = 0 \
min(D[i],D[i/3]) & i\pmod3 = 0 \end{cases} $

접근방식 1 (dp)

#include <iostream>
using namespace std;
int dp[1000000]={};
int main(){
    int n;
    cin >> n;
    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1]+1;
        if(!(i%3))dp[i]=min(dp[i],dp[i/3]+1);
        if(!(i%2))dp[i]=min(dp[i],dp[i/2]+1);
    }cout << dp[n];
}

접근방식 2 (bfs)

#include <bits/stdc++.h>
using namespace std;
int x,a[1000001]={};
bool seen[1000001]={};
queue<int> q;
void bfs(int i){
    if(seen[i]||i==0)return;
    seen[i]=true;
    if(i==1){
        q = queue<int>();
        return;
    }if(i%3==0){
        if(a[i/3]==0)a[i/3]=a[i]+1;
        else a[i/3]=min(a[i/3],a[i]+1);
        q.push(i/3);
    }if(i%2==0){
        if(a[i/2]==0)a[i/2]=a[i]+1;
        else a[i/2]=min(a[i/2],a[i]+1);
        q.push(i/2);
    }if(i-1>0){
        if(a[i-1]==0)a[i-1]=a[i]+1;
        else a[i-1]=min(a[i-1],a[i]+1);
        q.push(i-1);
    }
}
int main(){
    cin >> x;
    q.push(x);
    while(!q.empty()){
        int i=q.front();
        q.pop();
        bfs(i);
    }
    cout << a[1];
}