5. 백준 1463 1로 만들기 문제 공부

1. 문제를 풀면서

 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 다섯 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다.

2. 문제 출처 및 보기

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

3. 문제 해결

 이 문제도 동적 계획법의 문제이다. 다른 문제와 마찬가지로 이전 문제(작은 문제)의 해결로 현재 문제를 해결하는 방식으로 풀었다. 입력 값이 N이라면 '1 ~ (N-1)'의 해답을 이용해서 풀 수 있다. 해결 방법의 KEY로 주어진 값을 '-1'하거나 '/2', '/3'할 수 있다는 조건이 있다. 그러므로 func(N)은 1 + func(N-1), 1 + func(N/2), 1 + func(N/3) 중 하나일 것이다.  (단, func(X)는 X에서 1을 만드는데 계산되는 최소 횟수이다.) 이전에 구한 값을 다시 계산하지 않고 '저장&로드'했다. 이 때 주의할 점은 N은 자연수라는 것이다. 즉 -1, /2, /3 계산한 값이 자연수가 아니면 안된다는 조건을 주어야한다.

 

4. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1000001]{ 0 };
int main()
{
    int N;
 
    // 데이터 입력
    scanf("%d", &N);
 
    // 문제 해결 
    dp[1] = 0;
    for (int n = 2; n <= N; n++) {
        dp[n] = dp[n - 1] + 1;
        if (n % 3 == 0)
            dp[n] = min(dp[n], dp[n / 3] + 1);
        else if (n % 2 == 0)
            dp[n] = min(dp[n], dp[n / 2] + 1);
    }
 
    // 결과 출력
    printf("%d\n", dp[N]);
 
    return 0;
}