C++로 숫자 n을 1로 만드는 최소 연산 횟수 계산하기

문제 설명

임의의 숫자 n이 주어졌을 때, 다음 세 가지 연산 중 하나를 원하는 만큼 반복해서 수행할 수 있습니다.

n이 2로 나누어 떨어지면 n을 n/2로 바꿉니다.
n이 3으로 나누어 떨어지면 n을 2n/3으로 바꿉니다.
n이 5로 나누어 떨어지면 n을 4n/5로 바꿉니다.

목표는 이 숫자를 정확히 1로 만드는 것이며, 이때 필요한 최소 연산 횟수를 구해야 합니다. 만약 어떤 방법을 사용해도 1로 만들 수 없다면 -1을 반환합니다.

예시: n = 10

입력이 n = 10일 때 정답은 4입니다. 과정은 다음과 같습니다.

10 → 5 : n/2 연산 적용
5 → 4 : 4n/5 연산 적용
4 → 2 : n/2 연산 적용
2 → 1 : n/2 연산 적용

풀이 접근 방법

이 문제의 핵심은 각 연산의 실효 비용을 정확히 이해하는 것입니다.

n/2 연산: 인수 2를 하나 제거하며 비용은 1입니다.
2n/3 연산: 인수 3을 하나 제거하는 대신 인수 2가 새로 생기므로, 이후 n/2를 한 번 더 수행해야 합니다. 따라서 실효 비용은 2입니다.
4n/5 연산: 인수 5를 하나 제거하는 대신 인수 2가 두 개 생기므로, 이후 n/2를 두 번 더 수행해야 합니다. 따라서 실효 비용은 3입니다.

따라서 그리디 방식으로, 2로 나누어 떨어지면 가장 먼저 나누고, 그다음으로 3, 마지막으로 5를 처리하는 것이 최소 횟수를 보장합니다. 세 조건 모두에 해당하지 않으면 n은 2, 3, 5 이외의 소인수를 가지므로 더 이상 1로 만들 수 없으며, 이때 -1을 반환하고 종료합니다.

알고리즘 의사 코드

m := 0
n이 1이 아닌 동안 반복:
    n mod 2 = 0이면:
        n := n / 2
        m := m + 1
    아니면서 n mod 3 = 0이면:
        n := n / 3
        m := m + 2
    아니면서 n mod 5 = 0이면:
        n := n / 5
        m := m + 3
    그 외의 경우:
        m := -1
        반복문 탈출
m 반환

C++ 구현

위 알고리즘을 C++로 구현한 전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
   int m = 0;
   while (n != 1) {
      if (n % 2 == 0) {
         n = n / 2;
         m++;
      }
      else if (n % 3 == 0) {
         n = n / 3;
         m += 2;
      }
      else if (n % 5 == 0) {
         n = n / 5;
         m += 3;
      }
      else {
         m = -1;
         break;
      }
   }

   return m;
}

int main() {
   int n = 10;
   cout << solve(n) << endl;
}

입력

출력

복잡도 분석

매 반복마다 n은 최소 절반 이상으로 줄어들기 때문에 시간 복잡도는 O(log n)이며, 별도의 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.