BOJ 12852번: 1로 2 만들기 2

문제 설명

n에서 시작해서 1로 가는 최소 연산 횟수와 경로를 구하기.

사용할 수 있는 연산은:
-1
/2 (짝수일 때만)
/3 (3의 배수일 때만)

🔗 문제 링크

핵심 아이디어

1. d[i]를 i를 만들기 위한 최소 연산 횟수, pre[i]는 i를 만들기 위해 어떤 수에서 왔는지 기록한 경로 추적 배열로 두기
2. 먼저 i-1에서 +1 하는 방법으로 초기화한 후, i가 3의 배수이거나 2의 배수일 때를 고려하여 가장 작은 값으로 갱신
   
   

코드

#include <bits/stdc++.h>
using namespace std;
int d[1000005];
int pre[1000005];
int n;

int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    d[1] = 0;
    for(int i = 2; i <= n; i++){
        d[i] = d[i-1] + 1;
        pre[i] = i - 1;
        if (i % 2 == 0 && d[i] > d[i/2] + 1){ // -1보다 /2가 더 나은지 체크
            d[i] = d[i/2] + 1;
            pre[i] = i/2;
        }
        if (i % 3 == 0 && d[i] > d[i/3] + 1){ // -1보다 /3이 더 나은지 체크
            d[i] = d[i/3] + 1;
            pre[i] = i/3;
        }
    }
    cout << d[n] << '\n';
    int cur = n;
    while(true){
        cout << cur << ' ';
        if (cur == 1) break;
        cur = pre[cur];
    }
}

놓친 부분

• +1은 1번 연산한 거라는 뜻

추가 사항

• DP 뿐만 아니라 BFS에서도 비슷한 방식으로 경로 추적할 수 있다고 함

** 바킹독님 자료 참고: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/12852.cpp