백준 1463(1로 만들기)

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


동적계획법을 이용해 풀었습니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
 
 
int main(){
    int mem[1000001];
    int N;
    
    cin >> N;
    mem[1] = 0;
    for(int i = 2; i <= N; i++){
        mem[i] = mem[i-1]+1;
        if(i%2==0) mem[i] = min(mem[i],mem[i/2]+1);
        if(i%3==0) mem[i] = min(mem[i],mem[i/3]+1);
    }
    
    cout << mem[N];
    
    return 0;
}

bfs로도 풀 수 있을 거 같아서, bfs로도 한 번 풀어봤습니다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int bfs(int n) {
	bool visit[1000001];
	int idx=n;
    int count = 0;
    queue<int> q;
    q.push(n);
 
    while(1) {
        int size = q.size();
 
        for(int i=0; i<size; i++) {
            idx = q.front();
            q.pop();
            if(idx == 1)
                return count;        
            if(visit[idx-1] == 0) {
                q.push(idx-1);
                visit[idx-1] = 1;
            }
            if(idx%2 == 0 && visit[idx/2] == 0) {
                q.push(idx/2);
                visit[idx/2] = 1;
            }
            if(idx%3 == 0 && visit[idx/3] == 0) {
                q.push(idx/3);    
                visit[idx/3] = 1;
            }
        }
		
        count++;
    }
}
int main(){
	int n;
	cin >> n;
	
	cout << bfs(n);
	return 0;
}