[BaekJoon] 12852번 : 1로 만들기 2

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

문제

 

예시

 

풀이

• BFS를 사용할 수 있지만 DP를 활용하여 공간복잡도를 줄일 수 있습니다.
• if i%2 != 0 && i%3 != 0, D[i] = D[i-1]+1
• if i%2 == 0 && i%3 != 0, D[i] = min(D[i-1], D[i/2]) + 1
• if i%2 == 0 && i%3 == 0, D[i] = min(D[i-1], D[i/2], D[i/3]) + 1
• 방법을 출력하기 위해서는 그 전 숫자를 담는 prev 배열을 만들어야 합니다. 10 => prev[10] = 9, prev[9] = 3, prev[3] = 1

#include<iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int arr[1000005];
    int prev[10000005];
    
    arr[1] = 0;
    prev[1] = 0;
    
    int num;
    cin>>num;
    
    for(int i=2;i<=num;i++){
        arr[i] = arr[i-1]+1;
        prev[i] = i-1;
        if(i%2 == 0){
            if(arr[i]>(arr[i/2]+1)){
                arr[i] = arr[i/2]+1;
                prev[i] = i/2;
            }
        }
        
        if(i%3 == 0){
            if(arr[i]>(arr[i/3]+1)){
                arr[i] = arr[i/3]+1;
                prev[i] = i/3;
            }
        }
    }
    cout<<arr[num]<<"\n";
    
    do{
        cout<<num<<' ';
        num = prev[num];
    }while(num!=0);
}

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