[BOJ] 1463번 1로 만들기

문제

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

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

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

3. 1을 뺀다.

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

입력

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

출력

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

코드

• C++ 17 (최적화 전)

#include <iostream> #include <algorithm>   using namespace std;   int N;   // 이 문제는 n을 규칙을 사용하여 나누면 또 다른 n에 대한 문제가 된다. // 따라서 메모이제이션할 부분은 각 숫자에 대한 횟수이다. int Memo[1000001];   int dp(int n) {     // 점화식은 다음과 같다.     // Memo[n] = min(Memo[n - 1] + 1, Memo[n / 2] + 1 if n % 2 == 0, Memo[n / 3] + 1 if n % 3 == 0)          // 이미 메모이제이션 된 부분은 그대로 사용한다.     if (Memo[n] || n < 2)         return Memo[n];       // 점화식에 따라 코드를 작성한다.     Memo[n] = dp(n - 1) + 1;     if (n % 2 == 0)         Memo[n] = min(Memo[n], dp(n / 2) + 1);     if (n % 3 == 0)         Memo[n] = min(Memo[n], dp(n / 3) + 1);       return Memo[n]; }   int main() {     ios::sync_with_stdio(false);     cout.tie(nullptr);     cin.tie(nullptr);       // 메모이제이션     for (int i = 2; i <= 1000000; ++i)         dp(i);          cin >> N;     cout << Memo[N]; }

• C++17 (최적화 후)

#include <iostream> #include <algorithm>   using namespace std;   int N;   int dp(int n) {     // 이 문제는 좀 더 최적화 할 수 있다.     // 조금만 더 고찰해보면 1을 만들기 위해서는     // 1을 빼는 것보단 2나 3으로 숫자를 나누는 것이 훨씬 빠르다.     // 따라서, 1을 빼는 경우는 2나 3으로 나누어 떨어지지 않는 경우이다.     // 이를 코드로 옮기면 아래와 같다.     return (n < 2) ? 0 :         // n % 2와 n % 3을 하는 이유는 1을 빼는 것과 같기 때문이다.         min(dp(n / 2) + n % 2, dp(n / 3) + n % 3) + 1; }   int main() {     ios::sync_with_stdio(false);     cout.tie(nullptr);     cin.tie(nullptr);       cin >> N;     cout << dp(N); }

• C# 6.0

using System;   namespace ForAlgoCsharp {     class Program     {         static void Main(string[] args)         {             int n = Convert.ToInt32(Console.ReadLine());             Console.Write(dp(n));         }           static int dp(int n)         {             return (n < 2) ? 0 : Math.Min(dp(n / 2) + n % 2, dp(n / 3) + n % 3) + 1;         }     } }

• Python 3

N = int(input())   def dp(n):     return 0 if n < 2 else min(dp(n // 2) + n % 2, dp(n // 3) + n % 3) + 1   print(dp(N))

복기

DP 문제 중 처음으로 솔루션을 보지 않고 푼 문제라서 뿌듯하다. 솔직히 저기서 더 최적화가 이뤄질 줄은 몰랐는데, 다음에는 좀 더 고찰해봐야겠다.