[백준 1463] 1로 만들기

 

문제). 
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력)

첫째 줄에 1보다 크거나 같은 정수 N이 주어진다.

 

출력).

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

---

 

 

실행 예1).

 

입력)

Enter a number: 2

 

결과).

2 => 1
Result: 1

 

 

---

 

 

실행 예2).

 

입력)

Enter a number: 10

 

결과).

10 => 9 => 3 => 1
Result: 3

 

---

 

실행 예3).

 

입력)

Enter a number: 100

 

결과).

100 => 99 => 33 => 11 => 10 => 9 => 3 => 1
Result: 7

 

 

 

 

 

 

 

 

 

 

 

---

답은 아래에... ↓

 

 

 

 

 

 

 

---

 

 

 

 

 

스스로 풀어보시고... ↓

 

 

 

 

 

 

---

 

 

 

 

 

 

아래 답과 비교해보세요. ↓

 

 

 

 

 

 

---

프로그램 소스

#include <stdio.h>

int calculate(int value, int count)
{
    if(count == 0) {
        printf("%d", value);
    }
    
    /*값이 1이면 끝내기*/
    if(value == 1) 
    {
        return count;
    } 
    else if(value % 3 == 0) /* 3으로 나누어지면 */
    {
        printf(" => %d", value / 3);
        count = calculate(value /= 3, ++count);
    } 
    else if(value % 2 == 0) /* 2로 나누어지면 */
    {
        /* 1로 뺀 값이 9로 나누어지면 2로 나누는 것보다 처리 횟수가 같거나 유리함 */
        if((value - 1) % 9 == 0) 
        {
            printf(" => %d", value - 1);
            count = calculate(value - 1, ++count);
        } 
        else /* 그냥 2로 나누기 */
        {
            printf(" => %d", value / 2);
            count = calculate(value / 2, ++count);
        }
    } 
    else 
    {
        printf(" => %d", value - 1);
        count = calculate(value - 1, ++count);
    }
    return count;
}

int main()
{
    int value;
    int ret = 0;
    
    printf("Enter a number: ");
    scanf("%d", &value);
    
    ret = calculate(value, ret);
    printf("\nResult: %d\n", ret);
    return 0;
}