[백준/BOJ] 1463번: 1로 만들기 (동적 계획법) - C++ 문제 풀이

문제 설명

 

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

 

풀이

정수 N을 세 가지 연산을 반복 수행하여, 1로 만들기 위해서 필요한 최소한의 연산 수를 계산하는 문제이다.

1. N이 3으로 나누어 떨어지면, 3으로 나눈다.
2. N이 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

어디서부터 시작해야 할지 막막하다.

용어를 하나 정의해서 실마리를 잡아보자.

 

C(N)이 위의 세 가지 연산을 통해, 정수 N을 1로 만들기 위한 최소한의 연산 수라고 하자.

그럼,

C(1) = 0 ( 정수 1을 1로 만드는 데 필요한 연산은 없다 )

C(2) = 1

C(3) = 1 이 된다.

 

그리고, 다음 세 가지 C(N) 중 최소 값이 정답이 된다.

왜냐하면 처음 수행할 연산을 뺀, 최소 연산 수에 1을 더했을 뿐이므로 여전히 최소의 연산 수가 되기 때문이다.

 

N이 3으로 나누어 떨어지면 C(N) = C(N/3) + 1

N이 2로 나누어 떨어지면 C(N) = C(N/2) + 1

C(N) = C(N-1) + 1 ( 1을 빼는 연산 )

 

이렇게, 문제를 공식화하면 전체 문제를 작은 문제로 분할할 수 있다는 걸 알 수 있다.

이제 초기 값으로부터 순차적으로 최소 값들을 쌓아 올려 C(N)의 값을 구하면 된다.

동적 계획법을 사용하는 문제이다.

 

동적 계획법이란 전체의 문제를 작은 부분 문제로 나누어 계산한 후, 이 계산한 결과를 사용하여 전체의 문제를 빠르게 푸는 방법이다.

 

cache 버퍼를 마련해서 이전 결과 값을 저장 후, 재활용하는 방식으로 문제를 빠르게 푼다.

#define NUM 1000000
int cache[NUM+1];

int main(){

    int N;
    cin >> N;

    cache[1] = 0;	// 가장 작은 부분 문제의 결과 값
    cache[2] = 1;
    cache[3] = 1;

    int cnt = 0;

    for( int i = 4; i <= N; i++){
        
        cnt = cache[i-1];
        
        if ( i % 3 == 0){
            cnt = min( cache[i/3], cnt);
        } 
        
        if ( i % 2 == 0){
            cnt = min(cache[i/2], cnt);
        }
           
        cache[i] = cnt+1;	// 이전의 최소 연산 수에 이번 연산 수 1을 더한다
    }

    cout << cache[N];	// 주어진 N에 대한 최소 연산 수

    return 0;
}

 

 

소스 코드

#include <iostream>
using namespace std;

#define NUM 1000000
int cache[NUM+1];

int main(){

    int N;
    cin >> N;

    cache[1] = 0;
    cache[2] = 1;
    cache[3] = 1;

    int cnt = 0;

    for( int i = 4; i <= N; i++){
        
        cnt = cache[i-1];
        
        if ( i % 3 == 0){
            cnt = min( cache[i/3], cnt);
        } 
        
        if ( i % 2 == 0){
            cnt = min(cache[i/2], cnt);
        }
           
        cache[i] = cnt+1;
    }

    cout << cache[N];

    return 0;
}