[BaekJoon] 1463번 : 1로 만들기

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• BFS로 x/3, x/2, x-1 방향으로 모든 탐색하여 풀이를 작성할 수 있지만 메모리 초과로 다른 풀이 방법을 떠올려야 합니다.
• 이 문제는 DP를 이용하면 쉽게 풀 수 있습니다.

#include<iostream>
using namespace std;

int main(){
    int vec[1000001];
    int num;
    cin>>num;
    vec[1] = 0;
    for(int i=2;i<=num;i++){
        int n = 1000001;
        if(i%3==0){
            n = min(n, vec[i/3]+1);
        }
        
        if(i%2 == 0){
            n = min(n, vec[i/2]+1);
        }
        
        n = min(n, vec[i-1]+1);
        vec[i] = n;
    }
    
    cout<<vec[num];
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.