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

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

---

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

문제 설명:

정수 n이 주어졌을 때, n을 1로 만들기 위해 사용하는 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다:

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

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[1000001];

int main() {
    int n;
    cin >> n;
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + 1; // 1을 뺀 경우
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1); // 3으로 나눈 경우
        }
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1); // 2로 나눈 경우
        }
    }
    cout << dp[n];
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 이용하여 최소 연산 횟수를 계산합니다.
• 구현 세부사항:
  • dp[i]는 i를 1로 만들기 위한 최소 연산 횟수를 저장합니다.
  • 초기값: dp[1] = 0 (1은 이미 1이므로 연산이 필요 없습니다.)
  • 점화식:
    • dp[i] = dp[i - 1] + 1
    • i가 2로 나누어떨어지면 dp[i] = min(dp[i], dp[i / 2] + 1)
    • i가 3으로 나누어떨어지면 dp[i] = min(dp[i], dp[i / 3] + 1)
• 시간 복잡도: O(n)
  • 1부터 n까지 순차적으로 dp 값을 계산합니다.

---

결과

입력된 n에 대해 1로 만들기 위한 최소 연산 횟수를 출력합니다. 동적 프로그래밍을 사용하여 효율적으로 계산하였으며, 연산 범위가 커져도 안정적으로 작동합니다.

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