백준 12852번 [1로 만들기 2](C++)-yes6686- 티스토리

백준 문제 풀이: 12852 [1로 만들기 2]

---

문제 링크: https://www.acmicpc.net/problem/12852

문제 설명:

정수 N이 주어졌을 때, 다음 연산 중 하나를 반복해서 1로 만들려고 합니다:

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

이때, 연산을 사용하는 횟수를 최소화하고, 최소 횟수로 만들 수 있는 과정도 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <string>
using namespace std;

int dp[1000001];
string s[1000001];

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

    s[1] = "1"; // 초기 값 설정

    for (int i = 2; i <= n; i++) {
        int k;
        dp[i] = dp[i - 1] + 1; // 기본 연산: 1을 뺌
        k = i - 1;

        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i]) {
            dp[i] = dp[i / 2] + 1; // 2로 나누기
            k = i / 2;
        }

        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i]) {
            dp[i] = dp[i / 3] + 1; // 3으로 나누기
            k = i / 3;
        }

        s[i] = to_string(i) + " " + s[k]; // 최소 경로 저장
    }

    cout << dp[n] << '\n'; // 최소 연산 횟수 출력
    cout << s[n] << '\n'; // 경로 출력
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 활용하여 최소 연산 횟수를 구하고, 각 상태에서 최적의 경로를 기록합니다.
• 점화식:
  • dp[i] = dp[i - 1] + 1: 기본 연산 (1을 뺌)
  • dp[i] = dp[i / 2] + 1: 2로 나눌 경우
  • dp[i] = dp[i / 3] + 1: 3으로 나눌 경우
  • 이 중 최솟값을 선택하여 dp[i]와 최적의 이전 상태(k)를 갱신
• 구현 세부사항:
  • s[i] 배열을 사용하여 각 상태에서 경로를 기록
  • 출력 형식에 맞게 경로를 to_string으로 문자열로 저장
• 시간 복잡도: O(n)
  • 1부터 n까지 반복하며 각 상태에서 최대 3개의 연산을 확인

---

결과

주어진 정수 N을 최소 연산 횟수로 1로 만들고, 경로를 정확히 출력합니다. 동적 프로그래밍과 문자열 저장을 결합하여 문제를 효율적으로 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!