[C++] 1463번 1로 만들기

문제

https://www.acmicpc.net/problem/1463

---

풀이

1. 접근 방식

현재 숫자 i를 1로 만드는 최소 연산 횟수는 이전 숫자들의 연산 결과를 이용해 계산할 수 있음

DP 테이블 정의

• dp[i]: 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수

2. 점화식

숫자 i에서 가능한 연산을 고려하여 최소값을 계산

1. 1을 뺀 경우: dp[ i ]=dp[ i − 1 ] + 1
2. 2로 나눈 경우 (i가 2로 나누어 떨어질 때만): dp[ i ] = dp[ i / 2 ] + 1
3. 3으로 나눈 경우 (i가 3으로 나누어 떨어질 때만): dp[ i ] = dp[ i / 3 ] + 1

=> dp[ i ] = min⁡(dp[ i − 1 ] + 1, dp[ i / 2 ] + 1 (if  i % 2 == 0), dp[ i / 3 ] + 1 (if  i % 3 == 0))

---

코드

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

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n;
    cin >> n;

    // DP 배열 선언 및 초기화
    vector<int> dp(n + 1, 0);

    // DP 점화식 계산
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + 1; // 기본적으로 1을 빼는 연산

        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1); // 2로 나누는 경우와 비교

        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1); // 3으로 나누는 경우와 비교
    }

    // 결과 출력
    cout << dp[n] << endl;


    return 0;
}