백준 1463 / 1로 만들기

다이내믹 프로그래밍 연습 문제

해설을 듣기 전에 풀어보려고 시도했을 때 처음 했던 생각은 

N에서 1을 구하는 거보다 1에서 N을 구하는 연산이 더 쉽지 않을까해서 재귀로 짜봤는데 시간 초과가 떴다.

N의 범위가 꽤 크기 때문인 듯

다이내믹 프로그래밍 문제를 풀려면 우선 점화식을 짜야된다.

1로 만들기 문제의 점화석은 

D[N] = D[N/3] +1 (나누기 3이 가능할때)

       = D[N/2] +1 (나누기 2가 가능할때)

        = D[N-1] + 1

고로 

D[N] = min(D[N/3]+1, D[N/2]+1, D[N-1]+1) 이다. 피보나치랑 비슷하다.(?)

코드는

#include <stdio.h>
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
 
int n;
int ans = 200000000;
 
vector<int>d;
 
int check(int now) {
 
    if (now == 1) return 0;
    if (d[now] > 0) return d[now];
 
    d[now] = check(now - 1) + 1;
 
    if (now % 2 == 0) {
        int tmp = check(now / 2) + 1;
        if (d[now] > tmp) d[now] = tmp;
    }
    if (now % 3 == 0) {
        int tmp = check(now / 3) + 1;
        if (d[now] > tmp) d[now] = tmp;
    }
 
    return d[now];
 
}
 
int main() {
 
    
    cin >> n;
 
    d.resize(n+1);
 
    cout<< check(n);
 
    
 
}

처음에 1에서 N으로 만드는 알고리즘의 시간복잡도는 아마 O(N^3)인듯?? 재귀함수안에 호출 3개니까.

근데 위의 코드의 시간복잡도는 O(N). 훨씬 빠르다 볼 수 있다.