C 경우의 수

문제

필자가 좋아하는 것 중 하나가 금요일 저녁 퇴근길에 DVD나 만화책을 잔뜩 빌리고, 동네 슈퍼에 들려서 군것질거리를 사가지고 집에 들어가는 것이다. 오늘은 금요일이다. 현재 필자의 주머니에는 5천원이 있다. DVD 한편을 빌리면 3,500원이 남는다. 슈퍼에 들려서 크림빵(500원), 새우깡(700원), 콜라(400원)을 사려한다. 잔돈을 하나도 남기지 않고 이 세가지 물건을 하나 이상 반드시 구매하려면 어떻게 구매를 진행해야 하겠는가? 물론 여기에는 여러 가지 경우의 수가 있을 것이다. 필자가 어떠한 선택을 할 수 있는지 여러분이 제시해 주기 바란다.

실행 결과

현재 당신이 소유하고 있는 금액 : 3500
크림빵 1개, 새우깡 2개, 콜라 4개
크림빵 2개, 새우깡 3개, 콜라 1개
크림빵 4개, 새우깡 1개, 콜라 2개
어떻게 구입하시겠습니까?

해결

내용

이러한 문제는 재귀함수와 static 혹은 전역변수를 이용한 메모리 사용을 추가하여 푸는 방식이 일반적이다.

아래의 내가 푼 방법은 한 가지 해를 찾는 상황에서 신속하고 빠르지만 조건이 붙어있는 경우 재탐색이 매우 많아지게 되므로 비효율적이다.

코드

#include <stdio.h>
 
int main(void)
{
    int x=1, y=1, z=1;
    int p, q, r;
    int result;
    int result1, result2, result3;
    
    printf("현재 당신이 소유하고 있는 금액: ");
    scanf("%d", &result);
    
    result -= (500 + 700 + 400);
    
    p = result / 700;
    
    for(; p>=0; p--)
    {
        result1 = result - 700 * p;
        q = result1 / 500;
        
        for(; q>=0; q--)
        {
            if(q==1 && (result1 % 500) == 0){
                ++x;
                y += p;
                
                printf("크림빵 %d개, 새우깡 %d개, 콜라 %d개\n", x, y, z);
                x = 1;
                y = 1;
                z = 1;
                break;
            }

            result2 = result1 - 500 * q;
            r = result2 / 400;
            
            for(; r>=0; r--)
            {
                result3 = result2 - 400 * r;
                
                if((result3 % 400) != 0)
                {
                    continue;
                }
                else
                {
                    z += r;
                    x += q;
                    y += p;
                    
                    printf("크림빵 %d개, 새우깡 %d개, 콜라 %d개\n", x, y, z);
                    x = 1;
                    y = 1;
                    z = 1;
                    break;
                }
            }
        }
    }
    
    return 0;
}