문제
풀이
작은 수부터 큰 수까지 input까지 연산의 최솟값들을 저장해나갔다. 2로 나누어졌을 때의 연산자 갯수와 3로 나누어졌을 때의 연산자 갯수, 그리고 1을 뺐을 때 연산자 갯수들을 비교해가면서 최솟값들을 저장해나갔다. 2와 3으로 각각 나누어지지 않을 때는 큰 수로 대체하여 예외처리를 하였다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int main(){
int input;
scanf("%d", &input);
int dp[1000000];
dp[1] = 0;
for(int i = 2; i<=input; i++){
int num = i;
int cnt1 = 0 , cnt2 = 0, cnt3 = 0;
if(num % 2 == 0){
cnt1 = 1 + dp[num/2];
}
else if(num % 2 != 0){
cnt1 = 1000000;
}
if(num % 3 == 0){
cnt2 = 1 + dp[num/3];
}
else if(num % 3 != 0){
cnt2 = 1000000;
}
cnt3 = 1 + dp[num-1];
dp[i] = min(min(cnt1, cnt2), cnt3);
}
printf("%d\n", dp[input]);
}
