[BOJ알고리즘, C++]#1463_1로 만들기, DP, 동적 계획법

 

#1. 문제

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

1463번: 1로 만들기

 

---

#2. 풀이

 

1. DP, 동적 계획법

[알고리즘]#5_동적 계획법

 

동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나입니다. 동적 계획법은 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 방지해 알고리즘의 최적화를 수행합니다. 결과적으로, 동적 계획법을 통해 알고리즘의 최적화를 수행하고, 효율적으로 최적해를 찾아낼 수 있습니다.

 

2. 하위 문제의 결과 값들을 현재 문제를 해결하기 위해 어떻게 활용할 것인가?

 

1. 먼저, 해당 문제에 대한 DP의 전체 구조는 1부터 주어진 정수 X값으로 차례대로 Bottom-Up 하는 구조입니다.
2.  현재 정수에 대한 결과 값을 결정하는데 총 두 가지 하위 문제들이 있습니다. - (1) i-1 정수의 결과 값, (2-1) /2 정수의 결과 값 혹은 (2-2) /3 정수의 결과 값.
3. 따라서, 1부터 주어진 정수 X까지 차례대로 순회하며, 하위 문제들에 대한 결과 값을 기억하는 동시에 이를 토대로 현재 문제에 대한 결과 값을 경신해 줍니다.

 

---

 

#3. 코드

 

/*
 *   @문제 : 숫자 N을 /3, /2, -1 연산을 통해 1을 만들 수 있는 최소 연산 횟수 구하기
 *   @설명
 *           1. 먼저, dp[1] = 0번입니다.
 *           2. dp[i] 는 dp[i-1]+1번, dp[i/2]+1번, dp[i/3]+1번의 연산 횟수를 가집니다.
 *           3. 조건에 따라서, 위 세 가지 연산 중 어떠한 연산을 수행할지 결정하며 DP를 수행합니다.
 */

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

int N;
int dp[1000001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    dp[1] = 0;

    for (int i = 2; i <= N; ++i)
    {
        // #1. -1 연산
        dp[i] = dp[i - 1] + 1;
        // #2. /2 연산
        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);
        // #3. /3 연산
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);
    }

    cout << dp[N];

    return 0;
}

 

---