정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
입력 | 출력 |
---|---|
2 | 1 |
3 | 1 |
4 | 2 |
5 | 3 |
10 | 3 |
int dp[1000001];
int main(void) {
int n;
scanf("%d",&n);
for(int i=n;i>=1;i--){
if(i%3==0)dp[i/3]= dp[i/3]? min(dp[i]+1,dp[i/3]):dp[i]+1;
if(i%2==0)dp[i/2]= dp[i/2]? min(dp[i]+1,dp[i/2]):dp[i]+1;
if(i-1>0)dp[i-1]= dp[i-1]? min(dp[i]+1,dp[i-1]):dp[i]+1;
}
printf("%d\n",dp[1]);
return 0;
}
이전에 설탕 문제 풀어았던 걸 응용해서 풀어보았는데, 크게 어렵지 않아서 놀랐다!
점차 나아지는 모습이 보이니까 뿌듯하다.😌
앞으로도 뽜이링!