[백준 1463] 1로 만들기

문제 : 1로 만들기

문제 유형 : 다이나믹 프로그래밍

이 문제의 핵심은 입력 받은 수를 최소 횟수로 1로 만드는 것이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. X에서 1을 뺸다.

위 세가지를 이용해서 1로 만들어야 하는데 이를 어떻게 할까? 다이나믹 프로그래밍 문제를 풀 땐 너무 복잡하게 생각하면 오히려 안풀린다.

다이나믹 프로그래밍 문제를 풀기 위한 방법은 탑다운 방식과 바텀업 방식이 있다. 나도 공부하는 입장이니 두 가지 방법으로 설명하겠다.

1. 탑다운(Top-down) 방식

현재 수를 X라 하자. X가 3으로 나눠떨어진다면 X/3을 만드는 횟수는 X 만든 횟수에 한번더 연산을 한 것이기 때문에 X를 만든 횟수에 +1을 해주면 된다.

이와 마찬가지로 X가 2로 나눠 떨어진다면 X/2을 만드는 횟수는 X를 만드는 횟수에 +1을 하면 된다. 연산 3번도 마찬가지로 X를 만든 횟수에 +1한건 X-1을 만드는 횟수이다.

여기서 조심해야할껀 횟수의 최솟값을 만드는 것이기 때문에 +1 값이 그 다음 수를 만드는 수보다 작으면 갱신하게 만들면 된다.

탑다운 방식을 이용할 땐 dp배열을 10^6보다 큰 수로 채워놓으면 된다. (또는 값이 0일땐 그냥 대입해도 된다.)

시간복잡도 : O(N)

#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
 
ll dp[1000001];
const ll inf = 2000000;
 
int main()
{
    ll n;
    fill(dp, dp + 1000000, inf);
    cin >> n;
    dp[n] = 0;
    for (int i = n; i > 0; i--)
    {
        if (dp[i] == inf)continue;
        if (i % 3 == 0)dp[i / 3] = min(dp[i / 3], dp[i] + 1);
        if (i % 2 == 0)dp[i / 2] = min(dp[i / 2], dp[i] + 1);
        if (i >= 2)dp[i - 1] = min(dp[i - 1], dp[i] + 1);
    }
    cout << dp[1];
    return 0;
}

2. 바텀업(Buttom-up) 방식

탑다운과 거의 똑같은 풀이이다. 탑다운에서는 나눠 떨어지는지 확인을 했다면 바텀업에서는 그냥 곱하고 더하면 된다.

메모리를 좀 적게 써야한다 하면 곱했을때 구해야하는 값보다 크지 않을때만 넣어주면 된다. 하지만 이 문제는 10^6밖에 안되니 그냥 배열을 어느정도 크게 해놓고 계산을 하면 된다.

 - 메모리 생각해서 간단한 조건을 줬을 때 -시간복잡도 : O(N)

#include<iostream>
 
#define min(x,y) (x) < (y) && (x) != 0 && (y) != 0 ? (x) : (y)
 
int DP[1000001] = { 0 };
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++) {
        if (i + 1 <= n)DP[i + 1] = min(DP[i + 1], DP[i] + 1);
        if (i * 2 <= n) {
            DP[i * 2] = min(DP[i * 2],DP[i] + 1);
        }
        if (i * 3 <= n) {
            DP[i * 3] = min(DP[i * 3],DP[i] + 1);
        }
    }
    printf("%d", DP[n]);
    return 0;
}

 - 메모리 생각안하고 간단히 소스 코드 짰을 때 -시간복잡도 : O(N)

#include<iostream>
 
#define min(x,y) (x) < (y) && (x) != 0 && (y) != 0 ? (x) : (y)
 
int DP[3000001] = { 0 };
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++) {
        DP[i + 1] = min(DP[i + 1], DP[i] + 1);
        DP[i * 2] = min(DP[i * 2],DP[i] + 1);
        DP[i * 3] = min(DP[i * 3],DP[i] + 1);
    }
    printf("%d", DP[n]);
    return 0;
}