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

처음 접해본 DP 문제.

• 다이나믹 프로그래밍이란?
  
  점화식을 잘 세워서 한번 한 계산은 다시하지 않도록 효율적인 계산을 하게 만드는 프로그래밍

 

1463번 1로 만들기

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

 

이 문제는 주어진 숫자 n에서부터 top down 방식으로 내려오면 경우의 수가 너무 많아 시간이 오래 걸린다. 

1부터 시작해 bottom up 으로 올라가며 해당 숫자에 도달하는 최소의 경우를 계산해야 한다.

원리는, 1에서 2로 가는 최소 경로, 1에서 3으로 가는 최소 경로, 4로 가는 최소 경로 ... 이렇게 작은 문제푸터 풀어가는것이다.
4로 가는 최소 경로도 결국 2로 가는 최소 경로를 포함한다는 것을 이해하면 코드도 쉽게 이해할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

void find_min(int n , vector<int> &dp) {
    dp[n] = dp[n - 1] + 1;
    if (n % 2 == 0)
        dp[n] = min(dp[n / 2] + 1, dp[n]);
    if (n % 3 == 0)
        dp[n] = min(dp[n / 3] + 1, dp[n]);
}
int main() {

    int N;
    cin >> N;

    vector<int> dp(N + 1);

    dp[0] = 0;
    dp[1] = 0;
    for (int i = 2; i <= N; i++) {
        find_min(i, dp);
    }
    cout << dp[N] << '\n';
    return 0;
}

 

• vector STL 사용법

coding-factory.tistory.com/596

[C++] STL Vector 사용법 & 예제 총정리