[DP] 1로 만들기 (1463)(C++)

 

1. 문제 개요

 

정수 N이 주어졌을 때, N이 3으로 나누어 떨어지면 3으로 나누기, 2로 나누어 떨어지면 2로 나누기, N에서 1을 빼기, 이렇게 세 가지의 연산을 사용하여 N을 최대한 빠르게 1로 만드는 문제이다. 사용한 연산의 최솟값을 구한다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

다이나믹 프로그래밍을 통해 주어진 수를 1로 만들 수 있는 연산의 조합 중 최솟값을 구한다. 예를 들어, 주어진 수가 10인 경우, 10은 5에 2를 곱하거나, 9에 1을 더하여 만들 수 있다. 그렇다면 10이 1이 되는 최솟값은 숫자 5가 1이 되는 연산의 최솟값+1과 숫자 9가 1이 되는 연산의 최솟값 둘 중에 더 작은 값을 채택하면 된다. 이를 수식으로 나타내면 다음과 같다.

 

count[10] = min(count[9]+1, count[5]+1);

 

이때 count[9]와 count[5] 또한 동일한 방식으로 구하면 되는데, 재귀함수를 사용할 수 있다.

재귀함수 구현은 다음과 같이 할 수 있다.

 

const int max_val = 1000002;

int number_count(int n) {
    if(n==1)
        return 0;
    else if(count_list[n]!=0)
        return count_list[n];
    
    int three_value = max_val;
    int two_value = max_val;
    int one_value = max_val;
    
    if (n>=3 && n%3==0)
        three_value = number_count(n/3) + 1;
    if (n>=2 && n%2==0)
        two_value = number_count(n/2) + 1;
    one_value = number_count(n-1) + 1;
    
    count_list[n] = min(min(three_value, two_value),one_value);
    return count_list[n];
}

 

 

 

4. 전체 코드

 

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

int count_list[1000001];
const int max_val = 1000002;

int number_count(int n) {
    if(n==1)
        return 0;
    else if(count_list[n]!=0)
        return count_list[n];
    
    int three_value = max_val;
    int two_value = max_val;
    int one_value = max_val;
    
    if (n>=3 && n%3==0)
        three_value = number_count(n/3) + 1;
    if (n>=2 && n%2==0)
        two_value = number_count(n/2) + 1;
    one_value = number_count(n-1) + 1;
    
    count_list[n] = min(min(three_value, two_value),one_value);
    return count_list[n];
}

int main(void) {
    int N;
    scanf("%d",&N);
    printf("%d",number_count(N));
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!