백준 27440번 1로 만들기3 문제를 C++로 풀이한 내용입니다.

문제

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

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

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

입력

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

출력

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

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <map>
using std::cin;
using std::cout;
using std::map;
using std::min;

map<int, int> mem;

int min_ops(unsigned long long n)
{
    if (mem.find(n) != mem.end())
    {
        return mem[n];
    }

    mem[n] = min(min_ops(n / 2) + (n % 2), min_ops(n / 3) + (n % 3)) + 1;

    return mem[n];
}

int main()
{
    unsigned long long n;
    cin >> n;

    mem[1] = 0; // 초기값
    mem[2] = 1;

    cout << min_ops(n);
    return 0;
}

해설

이 문제는 주어지는 입력 범위가 매우 크기 때문에 단순한 방법으로는 풀기 어렵다. 1 부터 n까지의 모든 경우를 탐색하는 방법은 시간 복잡도가 O(N)이기 때문에 입력 범위가 10^18이라면 10^18번의 연산을 수행해야 한다. 이는 매우 비효율적이다. 따라서, 재귀식을 잘 활용하여 문제를 풀어야 한다.

1

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

min_ops는 주어진 정수 N을 1로 만들기 위해 사용할 수 있는 연산의 최솟값을 반환하는 함수이다. 이때, n / 2 의 값이 되기 위해 사용한 연산의 횟수는 min_ops(n / 2)이고, n % 2는 n을 2로 나눈 나머지이다. 나머지 값을 더해서 1을 뺀 값의 연산 횟수를 구할 수 있다. 이와 같은 방식으로 n / 3의 값을 구할 수 있다. 마지막에 1을 더해주는 이유는 연산의 횟수를 구할 때 사용한 연산 1회를 더해주기 위함이다.

위의 점화식을 사용하여 문제를 풀면, 주어진 정수 N을 1로 만들기 위해 사용할 수 있는 연산의 최솟값을 구할 수 있다. 이때, 중복되는 연산을 피하기 위해 메모이제이션을 사용한다.

시간 복잡도

재귀 호출을 할 때마다 n을 2로 나누거나 3으로 나누기 때문에 log n번의 연산을 수행하게 된다. 따라서, 시간 복잡도는 O(log n)이다.