백준 1463 - 1로 만들기

문제

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

풀이

이 문제의 경우 N을 1로 만드는 최소 횟수를 f(N) 이라 하면 점화식은 다음과 같이 나온다.

f(N) = min {

    0 (N=1일 때)

    f(N/3) + 1 (N이 3의 배수일 때)

    f(N/2) + 1 (N이 2의 배수일 때)

    f(N-1) + 1

} 

N/3, N/2, N-1을 했을 경우 연산의 횟수를 추가해야 하므로 + 1을 해준다.

 

코드

탑다운 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int dp[1000001];
 
int makeOne(int n)
{
    if (n == 1) return 0;
    if (dp[n] != -1) return dp[n];
 
    int result = makeOne(n - 1) + 1;
    if (n % 3 == 0)
        result = min(result, makeOne(n / 3) + 1);
    if (n % 2 == 0)
        result = min(result, makeOne(n / 2) + 1);
    dp[n] = result;
    return result;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    for (int i = 0; i < 1000001; i++)
        dp[i] = -1;
 
    int N;
    cin >> N;
 
    cout << makeOne(N);
 
    return 0;
}
 

 

 

바텀업 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int dp[1000001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) dp[i] = i - 1;
 
    for (int i = 2; i <= N; i++)
    {
        if (!(i % 3)) dp[i] = min(dp[i], dp[i / 3] + 1);
        if (!(i % 2)) dp[i] = min(dp[i], dp[i / 2] + 1);
        dp[i] = min(dp[i], dp[i - 1] + 1);
    }
 
    cout << dp[N];
 
    return 0;
}