[ 백준 12852- 1로 만들기 2 ]

### 문제 분석

1. DP
2. DP문제에서 경로를 파악 하고자 하는 경우의 기본 문제

시간 복잡도

구현

테이블 정의, 점화식 정의, 초기값 설정의 경우 이전에 풀었던 1로 만들기 문제와 같다.

경로 찾기

int R[1000002];
// R[i] 의 원소가 K 라면 : i에서 K로 가는 것이 최적이라는 의미이다.

for(int i = 3; i <= N; i++){

        // 1로 뺀 값
        T[i] = T[i-1] + 1;
        R[i] = i-1;

        // 3으로 뺀 값
        if(((i % 3) == 0) && T[i/3] + 1 < T[i]){
            T[i] = T[i/3] + 1;
            R[i] = i/3;
        }

        // 2로 뺀 값
        if(((i % 2) == 0) && T[i/2] + 1 < T[i]){
            T[i] = T[i/2] + 1;
            R[i] = i/2;
        }
        
    }

위의 코드와 같이 T[K]가 T[K-1], T[k/2], T[k/3]중에서 어느 곳으로 가는 것이 가장 최적인지 판단을 하고 그에 해당하는 값으로 R[K-1], R[k/2], R[k/3]도 값을 바꿔야한다.

이후

while(true){
        cout << cur << " ";
        if(cur == 1) break;
        cur = R[cur];
}

다음과 같은 코드를 통해서 경로를 순회 하면 경로를 추적 할 수 있다.

헤맸던 부분

R 배열에 대해서 초기값 설정을 잘못해서 무한 루프에 빠졌다.

얻은 것

DP 유형 학습 - 경로 찾기

전체 코드 [ 내 코드 ]

#include <iostream>
using namespace std;

int T[1000002]; // 1-indexed
int R[1000002]; // 1-indexed

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int N;

void get_input(){
    cin >> N;
}

void print_board(){
    for(int i = 1; i <= N; i++){
        cout << "i : " << i << " ";
        cout << R[i] << " ";
    }
    cout << "\n";
}


int main(void){
    init();
    get_input();

    // 초기값 설정
    T[1] = 0;
    T[2] = 1;
    R[1] = 0;
    R[2] = 1;

    for(int i = 3; i <= N; i++){

        // 1로 뺀 값
        T[i] = T[i-1] + 1;
        R[i] = i-1;

        // 3으로 뺀 값
        if(((i % 3) == 0) && T[i/3] + 1 < T[i]){
            T[i] = T[i/3] + 1;
            R[i] = i/3;
        }

        // 2로 뺀 값
        if(((i % 2) == 0) && T[i/2] + 1 < T[i]){
            T[i] = T[i/2] + 1;
            R[i] = i/2;
        }
    }

    int cur = N;

    // print_board();

    cout << T[N] << "\n";

    while(true){
        cout << cur << " ";
        if(cur == 1) break;
        cur = R[cur];
    }
    cout << "\n";

    return 0;
}

느낀점

1. 테이블 정의
2. 점화식 유도
3. 초기값 설정

3가지의 과정을 걸쳐서 문제를 풀이 한다는 것을 알고 있다고 해도 실제로 문제를 풀이 하는 것은 경험적인 측면이 많이 필요한 것 같다. 결국엔 많은 문제를 풀이하는 것 밖에는 답이 없는것 같다.

참조

바킹독님의 유튜브 강의

유튜브 강의 영상
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.