[백준 1463번] [동적 계획법] 1로 만들기

잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다.

 

다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다.

 

"dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면

점화식은

dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다.

다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1000001];

int recursion(int n){
    if(n == 1 || n == 2 || n == 3) return dp[n];
    if(dp[n - 1] == 0){
        recursion(n - 1);
    }
    if(n % 2 == 0 && dp[n / 2] == 0) recursion(n/2);
    if(n % 3 == 0 && dp[n / 3] == 0) recursion(n/2);
    if(n % 2 == 0 && n % 3 == 0){
        return dp[n] = min(min(dp[n - 1],dp[n / 2]), dp[n / 3]) + 1;
    }
    else if(n % 2 == 0){
        return dp[n] = min(dp[n - 1], dp[n / 2]) + 1;
    }
    else if(n % 3 == 0){
        return dp[n] = min(dp[n - 1], dp[n / 3]) + 1;
    }
    else{
        return dp[n] = dp[n - 1] + 1;
    }
}

int main(void){
    memset(dp, 0, sizeof(dp)); // 0으로 초기화
    int N;
    cin >> N;

    // Base case Setting
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;

    cout << recursion(N) << "\n";

    return 0;

}