[백준 1463] 1로 만들기 (C#, C++) - soo:bak

문제 링크

1463번 - 1로 만들기

설명

정수 N을 정해진 세 가지 연산만을 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 동적 프로그래밍 문제입니다.

사용 가능한 연산은 다음과 같습니다:

• 현재 숫자에서 1을 뺍니다.
• 현재 숫자가 2로 나누어떨어질 경우 2로 나눕니다.
• 현재 숫자가 3으로 나누어떨어질 경우 3으로 나눕니다.

이 연산들을 조합해 N을 1로 만드는 가장 적은 횟수를 찾아야 합니다.

핵심은 각 숫자에 대해 어떤 연산을 선택할지 판단하는 과정입니다.

접근법

작은 수부터 차례대로 최소 연산 횟수를 계산하여 저장하는 상향식 동적 프로그래밍 방식으로 풀이할 수 있습니다.

• 1은 이미 목표이므로 연산이 필요 없습니다.
  
• 2부터 N까지, 각 수를 1로 만들기 위한 최소 연산 횟수를 구합니다.
  
  

어떤 정수를 1로 만들기 위해 고려할 수 있는 세 가지 경우는 다음과 같습니다:

1. 바로 이전 수에서 1을 빼는 경우
   
   • 현재 수 - 1을 1로 만드는 데 필요한 최소 연산 횟수에 1을 더합니다.
     
2. 2로 나누어떨어지는 경우
   
   • 현재 수 ÷ 2를 1로 만드는 데 필요한 최소 연산 횟수에 1을 더합니다.
     
3. 3으로 나누어떨어지는 경우
   
   • 현재 수 ÷ 3를 1로 만드는 데 필요한 최소 연산 횟수에 1을 더합니다.
     

이 세 경우 중 가장 적은 연산 횟수를 선택하여 현재 수에 대한 값을 기록하면 됩니다.

예를 들어, 3 을 1 로 만드는 최적 경로는 3으로 나누기 연산 1회 입니다.

9 를 1 로 만드는 최적의 경로는 3으로 나누기 연산 1 회를 통해 3 으로 만든 후,

위에서 구한 3 이 1 이 되는 경로에서 필요한 최소한의 연산 1 회를 더한 경로 9 → 3 → 1

즉, 2 회의 연산이 필요한 경로가 최적의 경로입니다.

마찬가지로, 10을 1로 만드는 최적 경로는 10 → 9 → 3 → 1 (1 빼기, 3으로 나누기, 3으로 나누기)로 3회입니다.

따라서, 작은 수 부터 최적의 경로를 구하는 과정을 반복하면 전체적으로 시간 복잡도 O(N) 으로 풀이할 수 있습니다.

Code

[ C# ]

using System;

class Program {
  static void Main() {
    int n = int.Parse(Console.ReadLine());
    var dp = new int[n + 1];

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

    Console.WriteLine(dp[n]);
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

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

  int cache[1'000'001] = {0, };

  int num; cin >> num;
  for (int i = 2; i <= num; i++) {
    int res = cache[i - 1] + 1;
    if (i % 2 == 0) res = min(res, cache[i / 2] + 1);
    if (i % 3 == 0) res = min(res, cache[i / 3] + 1);
    cache[i] = res;
  }

  cout << cache[num] << "\n";

  return 0;
}