[백준] 1463번 - 1로 만들기

www.acmicpc.net

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

문제

💡

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

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

1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

시간 제한: 0.15초

메모리 제한: 128MB

입력

💡

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

💡

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력	예제 출력
2	1
10	3
56	5

풀이

연산 횟수가 가장 적은 경우는 특정한 규칙이 없어 모든 경우를 구해야 한다. 그래서 모든 경우를 저장하기 위해 타뷸레이션 방법을 사용했다. 또한, 시간 제한이 0.15초 (1500만)이므로 중복을 줄이기 위해 방문한 배열인지 확인했다.

코드


#include <iostream>
#include <vector>
using namespace std;

int recursive(vector<int>& dp, int n) {
    if (n == 1) {
        return 0;
    }

    if (dp[n] != -1) {
        return dp[n];
    }

    int result = recursive(dp, n - 1) + 1;

    if (n % 3 == 0) {
        result = min(result, recursive(dp, n / 3) + 1);
    }

    if (n % 2 == 0) {
        result = min(result, recursive(dp, n / 2) + 1);
    }

    dp[n] = result;
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    vector<int> dp(n + 1, -1);
    cout << recursive(dp, n);

    return 0;
}

다른 풀이

재귀가 꼭 필요할까 의문이 들어 다른 풀이를 살펴봤다. 반복문을 이용한 풀이를 살펴봤는데 재귀보다 복잡도가 훨씬 개선되어있었다.


#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> dp(n + 1, 0);

    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
    }
    cout << dp[n];
    return 0;
}