백준 2720번 풀이

문제

거스름돈을 최소한으로 주면 되는데 이제 미국돈… (25, 10, 5, 1을 조합하면 된다)

풀이

근데 문제는 둘째치고 달러랑 센트랑 뭔 상관인지는 알려주는게 인지상정 아닙니까… 미쿡돈 몰롸요우. 는 꺼무 검색해보고 알았는데 1달러가 100센트다. 그니까 쿼터는 25센트, 다임은 10센트, 니켈은 5센트, 페니는 1센트. 대충 우리나라 동전으로 치자면 500원 100원 50원 10원같은 느낌인거지 이제. 물론 우리나라 동전은 n배수 이런게 아닙니다.

import sys

T = int(sys.stdin.readline())
cent_list = [25, 10, 5, 1]

for i in range(T):
    change = int(sys.stdin.readline())

저 리스트는 내가 그냥 기억하기 쉬우라고 해둔거지 실제로 써먹지는 않음. 그나저나 이런 문제를 어디서 본 것 같다고요? 이거 그 예전에 설탕 배달하는데 5킬로 3킬로 맞췄던 그 문제랑 비슷하다. 그리디 알고리즘을 이용하는건데 이 알고리즘은 지금 당장 롸잇나우 정답일 수는 있어도 항상 정답은 아닌 그런 알고리즘이다. 그니까 지금은 어쩔 수 없었지만 나중에는 땅을 치고 후회하게 되는 뭐 그런 느낌인거다.

예를 들어서 나는 지금 너무 배고프고 주머니에 5000원이 있다고 치자. 그런데 마침 저기 타코야끼 트럭이 보인다. 그 옆에는 편의점도 있다. 그런데 타코야끼 트럭은 보니까 줄이 꽤 길어서 좀 기다려야 할 것 같고, 편의점은 꽤 한산해서 바로 계산이 된다. 근데 나는 지금 너어어어어어어어어어무 배가 고파서 웨이팅이 힘들다, 그러면 편의점 가서 뭘 먹는다.

이거 비슷한 케이스로는 소드실드 예약구매 하는 김에 스위치 같이 샀더니(배터리 개선판) 이듬해에 코로나 터져서 스위치 대란 터진거…? 그래서 본인 모동숲은 DL버전이다. 팩이 없으면 다운로드하면 된다 걍 필요해서 샀더니 본의아니게 신의 한수가 되었음…

import sys

T = int(sys.stdin.readline())
cent_list = [25, 10, 5, 1]

for i in range(T):
    quarter = 0
    dime = 0
    nickel = 0
    penny = 0
    change = int(sys.stdin.readline())
    while change >= 25:
        change -= 25
        quarter += 1
    while change >= 10:
        change -= 10
        dime += 1
    while change >= 5:
        change -= 5
        nickel += 1
    penny += change // 1
    print(quarter, dime, nickel, penny)

일단 딱히 뾰족한 수가 없어서 걍 while 때려박았다. 자, 생각해봅시다. 어떤 수가 25, 10, 5, 1로 나누어 떨어지지 않으려면 그 수보다 작아야 한다. 그러니까 25보다 큰 수는 일단 25로 나누고, 그 나머지를 10으로 나누고, 그 나머지를 5로 나누고, 그 나머지는 어차피 1의 자리이기 때문에 1의 자리에 걍 더하면 된다.

예를 들어서 124센트를 줘야 한다… 그러면 25보다 작은 수가 될 때까지 25를 계속 뺀다. 그러면 25를 네 번 빼면 남는건 24니까 25센트짜리는 4개가 된다. 다음으로 10보다 작은 수가 될 때까지 24에서 10을 계속 뺀다. 그러면 10센트 두 개를 빼고 4가 남고, 5보다 작을때까지 5를 빼야 하는데 이미 5보다 작기때문에 걍 페니 4개가 나오게 된다.

import sys

T = int(sys.stdin.readline())
cent_list = [25, 10, 5, 1]

for i in range(T):
    quarter = 0
    dime = 0
    nickel = 0
    penny = 0
    change = int(sys.stdin.readline())
    while change >= 25:
        quarter = change // 25
        change = change % 25
    while change >= 10:
        dime = change // 10
        change = change % 10
    while change >= 5:
        nickel = change // 5
        change = change % 5
    penny += change // 1

    print(quarter, dime, nickel, penny)

제줄한 건 아닌데, 아마 이런 식으로 나누기 해도 될거다.