[백준] [C++]12852번 1로 만들기 (dp, tracking)

1. 문제

 

12852번: 1로 만들기 2 (acmicpc.net)

12852번: 1로 만들기 2

 

2. 풀이

 

3가지 함수를 사용하여 1로 만드는 것

 

전형적인 dp문제로

 

모든 경우의 수를 따져

 

함수를 사용할때마다 1씩 더하면서

 

기저조건인 1이 나올경우 0을 리턴, 0이나올경우 max값을 리턴하도록 

 

함수를 짜면 문제없이 잘 동작할것이다.

 

 

이 문제는 또 과정을 추적해야한다.

 

과정을 추적하는 단순한 방법은 함수의 번호를 최적값과 같이 저장하는 것 이다.

 

코드는 다음과 같다.

 

 

 

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
 
using namespace std;
 
int one(int a);
int two(int a);
int three(int a);
 
int (*p[])(int a) = {one, two, three};
 
int cache[1000001];
int choice[1000001];
int MAX = 2000;
 
int toOne(int N) {
    if(N == 0) {
        return MAX;
    }
    if(N==1) {
        return 0;
    }
    if(cache[N]!= -1) {
        return cache[N];
    }
    cache[N] = MAX;
    for(int i = 2; i >= 0; i--) {
        int next = toOne((*p[i])(N)) + 1;
        if(cache[N] > next) {
            cache[N] = next;
            choice[N] = i;
        }
    }
    return cache[N];
}
void print(int N) {
    cout<<N<<" ";
    if(N == 1) {
        return;
    }
    return print((*p[choice[N]])(N));
}
 
int main() {
    int N;
    cin >> N;
    memset(cache, -1, sizeof cache);
    memset(choice, -1, sizeof choice);
    cout<<toOne(N)<<"\n";
    print(N);
}
int one(int a) {
    if(a%3 == 0) {
        return a/3;
    }
    return a;
}
int two(int a) {
    if(a%2 == 0) {
        return a/2;
    }
    return a;
}
int three(int a) {
    return a - 1;
}