-
[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)); }
아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!
'BOJ C++ 알고리즘 공부' 카테고리의 다른 글
[DP] 동물원 (1309)(C++) (0) 2024.01.28 [DP] 오르막 수 (11057)(C++) (1) 2024.01.24 [에드혹] 오락실에 간 총총이 (26071)(C++) (0) 2023.06.01 [이분탐색] 가장 긴 증가하는 부분 수열 2(12015)(C++) (1) 2023.03.17 [이분탐색] K번째 수(1300)(C++) (0) 2023.03.16