문제). 
정수 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;
}

 

 

 

 

 

블로그 이미지

사용자 자연&사람

행복한 개발자 programmer since 1995.

댓글을 달아 주세요