[C++] BOJ_1463 1로 만들기

문제: 백준 1463 (c++)

풀이과정

우선 이 문제를 처음 봤을 때 이미 dp라는 것을 알고 접근했다. 그러나 아무리 생각해 봐도 도저히

10이 있을 때 바로 2로 나누는 것이 아닌 1을 먼저 뺌으로써

10이 1로 되기까지의 연산 횟수의 최솟값을 구하는 방법을 생각하는 데 어려움을 겪었다.

구글링을 통해 정보를 얻고 난 후에야 풀 수 있었다.

코드를 보면 알 수 있듯이 피보나치가 떠오르는 방식으로 풀었다.

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

int main() {
    int n ;
    int dp[1000001] ;

    cin >> n ;

    dp[0] = 0 ;
    dp[1] = 0 ;

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

    cout << dp[n] ;
}

우선적으로 1을 빼는 경우를 먼저 배열에 넣어주고

2 또는 3으로 나누어질 때의 조건문에서 min을 이용하여 연산의 최솟값을 구할 수 있도록 해주었다.

Dynamic Programming(동적 계획법)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식

dp의 조건으로는 두 가지가 있다.

• 최적 부분 구조
• 부분 반복 문제
  
  

Dynamic Programming의 접근 방식

• Top-down (재귀, Memoization): 문제를 위에서 아래로 접근하여 문제를 쪼개가며 해결해 나가는 방식
• Bottom-up (반복문, Tabulation): 문제를 아래서부터 접근하여 점차 큰 문제를 해결해 나가는 방식