ABOUT ME

척척학사가 되고 싶은 AI 꿈나무의 블로그

Today
Yesterday
Total
  • [DP] 1로 만들기 (1463)(C++)
    BOJ C++ 알고리즘 공부 2024. 1. 22. 17:01

     

    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));
    }

     

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

     

    댓글

Designed by Tistory.