[dp, bfs] 백준 16568 엔비스카의 영혼

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

이번 문제는 전에 풀었던 백준 1463(1로 만들기) 문제를 생각해서 풀었습니다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int dp[1000002]={0};
    int n,a,b;
    
    cin >> n >> a >> b;
    
    for(int i = 1; i <= n; i++){
        dp[i] = 1000001;
    }
    
    if(b > a){
        int tmp = a;
        a =b; b=tmp;
    }
    
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i-1]+1;
        if(i-a-1 >= 0) dp[i] = min(dp[i],dp[i-a-1]+1);
        if(i-b-1 >= 0)   dp[i] = min(dp[i],dp[i-b-1]+1);
 
    }
    cout << dp[n];
} 

bfs로도 풀어봤습니다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
int bfs(int n, int a, int b){
    bool visited[1000001] = {};
    queue<int> q;
    int idx= n;
    int t = 0;
    q.push(n);
    
    while(1){
        int size = q.size();
        
        for(int i = 0; i < size; i++){
            idx = q.front();
            q.pop();
            
            if(idx==0)
                return t;
            if(!visited[idx-1]){
                q.push(idx-1);
                visited[idx-1] = 1;
            }
            if(idx-a-1 >= 0 && visited[idx-a-1] == 0){
                q.push(idx-a-1);
                visited[idx-a-1] = 1;
            }
            if(idx-b-1 >= 0 && visited[idx-b-1] == 0){
                q.push(idx-b-1);
                visited[idx-b-1] = 1;
            }
        }
        
        t++;
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    
    int n,a,b;
    
    cin >> n >> a >> b;
    
    
    
    cout << bfs(n,a,b);
}