[백준][1463] 1로 만들기
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세가지 이다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다.
- X가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
입력 1
2
출력 1
1
입력 2
10
출력 2
3
힌트
10의 경우에 10 -> 9 -> 3 -> 1 로 3번만에 만들 수 있다.
1. 문제 설명
- 해당 문제는 DP로 푸는 문제이다.
나는 Bottom-Up 방식을 이용하여 풀었다. (아래부터 올라오는 반복문 형식)
예시로
n = 6
일 경우,
dp[1] = 1
,dp[2] = 2
,dp[3] = 1
,dp[4] = 2
,dp[5] = 3
,dp[6] = 2
가 되도록 한다.dp[6]
은dp[3] = 1
값을 얻어와서+1
해주는 형식으로 코드를 짰다.- [점화식]
1번 규칙 (3으로 나누어 떨어진다) :dp[n] = dp[n / 3] + 1
2번 규칙 (2로 나누어 떨어진다) :dp[n] = dp[n / 2] + 1
3번 규칙 (1을 뺀다) :dp[n] = dp[n - 1] + 1
2. 소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> dp(n + 1, 0);
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 2 == 0) {
dp[i] = min(dp[i / 2] + 1, dp[i]);
}
if (i % 3 == 0) {
dp[i] = min(dp[i / 3] + 1, dp[i]);
}
}
cout << dp[n] << endl;
return 0;
}