CS50 Probelm set 1 - 동전 거스름돈 문제

dondonee·2023년 1월 18일

CS50

목록 보기

3/12

동전 거스름돈 문제

탐욕 알고리즘

탐욕 알고리즘이란 최적의 해법을 찾기 위해 지역적으로 최선의 방법을 선택하는 것을 반복함으로써, 전역적으로도 최선의 방법을 찾아내는 방법이다. 하지만 위의 이미지처럼 당장에 가장 좋은 선택을 한다고 해서 최종적으로도 반드시 가장 좋은 선택이 되는 것은 아니다. 욕심에 눈이 멀어 전체를 보지 못하고 당장 최선의 이익만을 탐하는 모습과 닮아 탐욕 알고리즘이라는 명칭이 붙었을 것이다.

According to the National Institute of Standards and Technology (NIST), a greedy algorithm is one “that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for some optimization problems, but may find less-than-optimal solutions for some instances of other problems.”

우리는 보통 거스름돈을 받을 때 가능한 최소한의 동전을 받고 싶어한다. 이런 문제에서는 탐욕 알고리즘이 최적의 방법을 찾아준다. 직원이 손님에게 41센트를 거슬러주어야 하는 상황을 생각해보자. 25센트, 10센트, 5센트, 1센트 네 가지의 동전을 사용할 수 있고 동전이 충분히 많을 때, 직원은 일단 가장 큰 단위의 동전인 25센트 짜리로 얼마나 거슬러 줄 수 있는지 생각해 볼 것이다. 직원의 문제는 거스름을 한 단계씩 반복하여 나머지를 0센트로 만드는 것이고, 25센트는 그 최종점에 가장 빨리 도달하게 해 주기 때문이다. 25센트 동전 1개를 사용하면 16센트가 남는다. 10센트 동전 1개를 사용하면 6센트가 남는다. 이어서 5센트 동전 1개를 주고 1센트가 남고, 1센트 동전 1개를 주면 0센트가 된다. 총 사용된 동전은 4개이다.

Cash 과제

지시 사항

사용자에게 거슬러주어야 할 금액을 입력받는다
최소 동전의 개수를 계산하여 출력한다

가이드

$9.75의 경우 사용자는 9.75와 같이 입력해야 한다. $9.75나 975이면 안 된다. 반면 딱 $9라면, 사용자는 9.00 또는 9로 입력해야 한다. $9 또는 900으로 입력해서는 안 된다. 하지만 C언어의 float 자료형은 부동소수점 방식을 사용하기 때문에 값을 자동적으로 9.0이나 9.000으로 잘 처리해줄 것이다. 사용자가 적절한 형식으로 입력하는지 체크하는 방법에 대해서는 고민하지 않아도 된다.
get_float은 값이 float 자료형에 맞는지 체크해주기 때문에 사용자의 입력값이 너무 크지 않을지는 걱정하지 않아도 된다. 단 get_float은 값이 음수인지 체크하지는 않는다.
사용자가 음수가 아닌 값을 입력하는지 체크해여야 하며, 적절한 값을 입력하지 않는 경우 올바른 값을 입력할 때까지 반복해서 프롬프트를 주어야 한다.
마지막 라인에 출력해야 할 값은 최소한으로 거슬러줄 수 있는 동전의 개수이며, \n을 이용해 줄바꿈을 해야 한다.
부동소수점 방식의 한계를 유의할 것. float 타입의 x(=2)와 y(=10)을 가지고 x / y를 계산하면 결과는 0.20이 아니다.
round를 이용해 센트를 penny(1센트) 단위로 변환할 것. round는 인수를 가장 가까운 정수로 변환해주는 함수로, math.h에 정의되어 있다.
- round(0.75) → 1

풀이

/*
    $$ Pseudocode :
    1. 사용자에게 바꿔주어야 할 금액을 입력받는다. 예) 9.75 (float)
        1-1. 음수가 아닌지 확인한다.
        1-2. 조건에 맞지 않는 경우 1로 돌아가 프롬프트를 다시 출력한다.
    2. int 변수에 입력받은 금약을 1페니 단위로 변환하여 저장한다. (float의 나눗셈은 부동소수점 부정확성 때문에 정확한 결과가 나오지 않는다)
    3. 큰 동전부터 사용해 거슬러준다. 사용되는 동전: 25센트, 10센트, 5센트, 1센트 (총 4종류)
        3-1. 25센트 동전을 사용해 나눈다.
        3-2. 몫을 int type 변수 minimum에 가산한다.
        3-3. 나머지를 계산한다.
            3-3-a. 나머지가 0인 경우 반복문을 탈출한다.
        3-4. 나머지 값을 받아 10, 5, 1센트 차례로 반복한다.
    4. minimum을 반환한다. 
*/

int whittleDown(int);

int main(void)
{
    float owed;
    bool check = true;
    int minimum = 0;

    // Prompt the user for a change owed
    do
    {
        owed = get_float("Change owed: ");

        if (owed >= 0)
        {
            check = false;
        }

    } while (check);

    // Convert the user's inputted dollars to cents
    int coins = round(owed * 100); // round(): 가장 가까운 정수로 변환. 예) 0.75 -> 1

    // Print result(minimum)
    minimum = whittleDown(coins);
    printf("%i\n", minimum);
}

int whittleDown(int dividend)
{
    int coinTypes[4] = {25, 10, 5, 1};
    int remainder = dividend;
    int result = 0;

    for (int i = 0; i < 4; i++)
    {
        int size = coinTypes[i];
        int quotient = remainder / size;
        remainder = remainder - (size * quotient);

        result += quotient;

        if (remainder == 0)
        {
            i = 999;
        }
    }

    return result;
}