백준 27440번 “1로 만들기 3"은 10^18 범위의 매우 큰 정수를 세 가지 연산(3으로 나누기, 2로 나누기, 1 빼기)을 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 문제로, 입력 범위가 10^18에 달하기 때문에 일반적인 동적 프로그래밍 접근법(O(N) 시간, O(N) 공간)으로는 해결이 불가능하며, 재귀적 점화식과 해시 맵 기반 메모이제이션을 활용하여 O(log² n) 시간 복잡도로 효율적으로 해결해야 한다.

문제 설명

백준 27440번 - 1로 만들기 3

정수 N이 주어졌을 때, 세 가지 연산을 적절히 사용하여 1을 만드는 데 필요한 최소 연산 횟수를 구하는 문제다.

사용 가능한 연산

정수 X에 대해 다음 세 가지 연산을 사용할 수 있다.

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

입력

첫째 줄에 1 이상 10^18 이하의 정수 N이 주어진다.

출력

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

예제

입력출력설명
212 → 1 (2로 나누기)
10410 → 9 → 3 → 1 (빼기 → 3나누기 → 3나누기 → 3나누기)

문제 분석

기본 동적 프로그래밍 접근법의 한계

“1로 만들기” 문제의 기본 버전(백준 1463번)은 N이 최대 10^6으로, 1부터 N까지 모든 값에 대해 최소 연산 횟수를 계산하는 O(N) 동적 프로그래밍으로 해결할 수 있다.

// 기본 DP: O(N) 시간, O(N) 공간
dp[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);
}

그러나 이 문제에서 N의 범위가 10^18이므로, 이 접근법은 메모리(약 8 엑사바이트 필요)와 시간(약 3만 년 소요) 모두에서 실현 불가능하다.

핵심 관찰

문제를 효율적으로 해결하기 위한 핵심 관찰은 다음과 같다.

관찰 1: 2나 3으로 나누는 것이 1을 빼는 것보다 효율적이다

n을 1로 만들기 위해서는 결국 n을 충분히 작은 수로 줄여야 하며, 나눗셈은 한 번에 n을 절반 또는 1/3로 줄이는 반면 뺄셈은 1만 줄이므로, 가능하면 나눗셈을 선택하는 것이 유리하다.

관찰 2: 1 빼기 연산은 나눗셈을 가능하게 하기 위해 사용한다

n이 2나 3으로 나누어 떨어지지 않으면 1을 빼서 나누어 떨어지게 만들어야 하며, 이 경우 n % 2 또는 n % 3번의 빼기 연산이 필요하다.

관찰 3: n에서 가장 가까운 2의 배수와 3의 배수를 비교한다

n에서 n/2에 도달하려면 n % 2번 빼고 2로 나누면 되고, n/3에 도달하려면 n % 3번 빼고 3으로 나누면 된다. 둘 중 더 적은 연산으로 1에 도달하는 경로를 선택한다.

알고리즘 설계

점화식 유도

위 관찰을 바탕으로 다음과 같은 점화식을 유도할 수 있다.

핵심 점화식

f(n) = min(f(n/2) + n%2, f(n/3) + n%3) + 1

n을 1로 만드는 최소 연산 횟수는, (1) n/2로 가는 경로와 (2) n/3으로 가는 경로 중 더 적은 연산이 필요한 경로를 선택하고 1을 더한 값이다.

각 항의 의미는 다음과 같다.

  • f(n/2) + n%2: n에서 n/2로 가기 위해 필요한 빼기 연산(n%2번) + n/2에서 1로 가는 최소 연산 + 2로 나누기 1회
  • f(n/3) + n%3: n에서 n/3로 가기 위해 필요한 빼기 연산(n%3번) + n/3에서 1로 가는 최소 연산 + 3으로 나누기 1회
  • + 1: 마지막 나눗셈 연산 1회

메모이제이션의 필요성

이 점화식은 n/2와 n/3을 재귀적으로 호출하므로, 같은 값에 대한 중복 계산이 발생할 수 있다. 예를 들어 f(12)를 계산할 때 f(6)과 f(4)가 호출되고, f(6)에서는 f(3)과 f(2)가, f(4)에서는 f(2)와 f(1)이 호출되어 f(2)가 중복 계산된다.

해시 맵(C++의 std::map 또는 std::unordered_map)을 사용한 메모이제이션으로 이미 계산한 값을 저장하면 중복 계산을 방지하여 효율성을 크게 향상시킬 수 있다.

구현

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

map<long long, long long> memo;

long long solve(long long n) {
    if (n == 1) return 0;
    if (memo.count(n)) return memo[n];

    long long via2 = solve(n / 2) + (n % 2) + 1;
    long long via3 = solve(n / 3) + (n % 3) + 1;

    return memo[n] = min(via2, via3);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    cout << solve(n) << '\n';

    return 0;
}

코드 설명

  • memo: 이미 계산한 결과를 저장하는 해시 맵으로, 키는 정수 n이고 값은 n을 1로 만드는 최소 연산 횟수이다.
  • solve(n): n을 1로 만드는 최소 연산 횟수를 반환하는 재귀 함수로, n이 1이면 0을 반환하고, 이미 계산된 값이 있으면 그 값을 반환하며, 그렇지 않으면 점화식을 적용하여 계산한다.
  • via2: n/2 경로로 가는 데 필요한 총 연산 횟수 (n%2번 빼기 + n/2를 1로 만들기 + 2로 나누기)
  • via3: n/3 경로로 가는 데 필요한 총 연산 횟수 (n%3번 빼기 + n/3을 1로 만들기 + 3으로 나누기)

최적화된 구현

std::unordered_map을 사용하면 평균 O(1)의 조회/삽입 시간으로 성능을 향상시킬 수 있다.

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

unordered_map<long long, long long> memo;

long long solve(long long n) {
    if (n == 1) return 0;

    auto it = memo.find(n);
    if (it != memo.end()) return it->second;

    return memo[n] = min(
        solve(n / 2) + (n % 2),
        solve(n / 3) + (n % 3)
    ) + 1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    cout << solve(n) << '\n';

    return 0;
}

시간 복잡도 분석

재귀 호출 깊이

각 재귀 호출에서 n은 최소한 절반 이상 감소하므로(n/2 또는 n/3), 재귀 호출 깊이는 O(log n)이다.

고유한 상태의 수

각 재귀 호출에서 두 개의 하위 문제(n/2와 n/3)가 생성되며, 깊이가 O(log n)이므로 최대 2^(log n) = n개의 상태가 가능해 보이지만, 실제로는 훨씬 적은 수의 고유한 상태만 생성된다. 이는 많은 경로가 같은 값으로 수렴하기 때문이며, 실제 고유 상태 수는 O(log² n) 정도이다.

전체 시간 복잡도

std::map을 사용할 경우 각 조회/삽입에 O(log(상태 수)) = O(log log n) 시간이 소요되므로 전체 시간 복잡도는 O(log² n × log log n)이다. std::unordered_map을 사용하면 평균 O(log² n)의 시간 복잡도를 달성할 수 있다.

자료 구조조회/삽입전체 시간 복잡도
std::mapO(log log n)O(log² n × log log n)
std::unordered_mapO(1) 평균O(log² n) 평균

공간 복잡도

메모이제이션에 사용되는 해시 맵의 크기가 고유 상태 수에 비례하므로 공간 복잡도는 O(log² n)이다. N = 10^18일 때 log₂(10^18) ≈ 60이므로, 최대 약 3600개의 상태만 저장하면 되어 메모리 사용량이 매우 적다.

알고리즘의 정당성

최적 부분 구조

이 문제는 최적 부분 구조(Optimal Substructure) 성질을 가진다. n을 1로 만드는 최적해는 반드시 n/2 또는 n/3(나눗셈 가능 시) 또는 n-1을 1로 만드는 최적해를 포함하며, 따라서 부분 문제의 최적해를 조합하여 전체 최적해를 구할 수 있다.

점화식의 정당성

점화식 f(n) = min(f(n/2) + n%2, f(n/3) + n%3) + 1이 올바른 이유는 다음과 같다.

  1. n/2 경로: n에서 2로 나눌 수 있는 가장 가까운 수는 n - (n%2)이며, 여기서 2로 나누면 n/2가 된다. 따라서 빼기 n%2회 + 나누기 1회 = n%2 + 1회의 연산이 필요하다.

  2. n/3 경로: 마찬가지로 3으로 나눌 수 있는 가장 가까운 수는 n - (n%3)이며, 빼기 n%3회 + 나누기 1회 = n%3 + 1회의 연산이 필요하다.

  3. 두 경로 중 더 적은 연산이 필요한 경로를 선택하면 최적해를 얻는다.

관련 문제와 확장

1로 만들기 시리즈

백준에는 “1로 만들기” 문제가 여러 버전으로 존재하며, 각각 다른 접근법이 필요하다.

문제 번호N 범위권장 접근법
1463≤ 10^6일반 DP
12852≤ 10^6DP + 경로 추적
27440≤ 10^18재귀 + 메모이제이션

변형 문제

이 알고리즘의 아이디어는 다른 유사한 문제에도 적용할 수 있다.

  • 연산의 종류가 다른 경우 (예: 5로 나누기 추가)
  • 연산에 비용이 다른 경우 (예: 3으로 나누기는 비용 2)
  • 목표 값이 1이 아닌 경우

결론

백준 27440번 “1로 만들기 3"은 10^18 범위의 큰 수를 다루어야 하므로 일반적인 O(N) 동적 프로그래밍으로는 해결할 수 없으며, 재귀적 점화식과 해시 맵 기반 메모이제이션을 활용하여 O(log² n) 시간에 해결해야 한다. 핵심 아이디어는 n에서 n/2와 n/3으로 가는 두 경로를 비교하여 더 효율적인 경로를 선택하는 것이며, 메모이제이션을 통해 중복 계산을 방지한다. 이 문제는 동적 프로그래밍의 기본 아이디어를 확장하여 매우 큰 입력 범위를 처리하는 방법을 보여주는 좋은 예시이다.