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

문제 링크

12852번 - 1로 만들기 2

설명

정수 N이 주어지는 상황에서, N (1 ≤ N ≤ 1,000,000)이 주어질 때, N을 1로 만드는 최소 연산 횟수와 그 과정에서 거치는 모든 수를 구하는 문제입니다.

사용할 수 있는 연산은 세 가지입니다:

• N이 3으로 나누어떨어지면 3으로 나눕니다
• N이 2로 나누어떨어지면 2로 나눕니다
• 1을 뺍니다

첫째 줄에 연산 횟수의 최솟값을 출력하고, 둘째 줄에 N부터 1까지의 과정에 포함되는 수를 순서대로 출력합니다.

접근법

동적 프로그래밍으로 최소 연산 횟수를 구하고, 부모 배열을 사용하여 경로를 역추적합니다.

먼저 dp[i]를 i를 1로 만드는 최소 연산 횟수로 정의합니다. dp[1] = 0으로 초기화하고, 2부터 N까지 차례대로 계산합니다.

각 수 i에 대해 세 가지 연산을 고려합니다. 기본적으로 dp[i] = dp[i-1] + 1로 설정합니다. i가 2로 나누어떨어지면 dp[i/2] + 1과 비교하여 더 작은 값으로 갱신합니다. i가 3으로 나누어떨어지면 dp[i/3] + 1과도 비교합니다.

이후, 경로를 복원하기 위해 parent[i] 배열을 사용합니다. dp[i]를 갱신할 때마다 어떤 수에서 왔는지를 parent[i]에 저장합니다. 예를 들어 i-1에서 왔다면 parent[i] = i-1, i/2에서 왔다면 parent[i] = i/2로 설정합니다.

모든 계산이 끝나면 N에서 시작하여 parent 배열을 따라가며 1에 도달할 때까지 수를 출력합니다.

예를 들어, N = 10인 경우:

10 → 9 (10-1) → 3 (9/3) → 1 (3/3)로 3번의 연산으로 1을 만들 수 있습니다. dp[10] = 3이고, 경로는 [10, 9, 3, 1]입니다.

다른 경로인 10 → 5 (10/2) → 4 (5-1) → 2 (4/2) → 1 (2/2)은 4번의 연산이 필요하므로 최적이 아닙니다.

2부터 N까지 순회하므로 시간 복잡도는 O(N)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var dp = new int[n + 1];
      var parent = new int[n + 1];

      for (var i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        parent[i] = i - 1;

        if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
          dp[i] = dp[i / 2] + 1;
          parent[i] = i / 2;
        }
        if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
          dp[i] = dp[i / 3] + 1;
          parent[i] = i / 3;
        }
      }

      Console.WriteLine(dp[n]);
      var cur = n;
      while (cur != 0) {
        Console.Write(cur + " ");
        if (cur == 1)
          break;
        cur = parent[cur];
      }
      Console.WriteLine();
    }
  }
}

C++

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

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

  int n; cin >> n;
  vector<int> dp(n + 1), parent(n + 1);

  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;
    parent[i] = i - 1;

    if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) {
      dp[i] = dp[i / 2] + 1;
      parent[i] = i / 2;
    }
    if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
      dp[i] = dp[i / 3] + 1;
      parent[i] = i / 3;
    }
  }

  cout << dp[n] << "\n";
  for (int cur = n; ; cur = parent[cur]) {
    cout << cur << " ";
    if (cur == 1)
      break;
  }
  cout << "\n";

  return 0;
}