python 백준 2091 동전

로직

• 동전은 1원, 5원, 10원, 25원이 존재

• 비싼 동전부터 동전을 최소한으로 사용하는 방식

  • 25원 동전이 d개 만큼은 가지고 있어야 나머지 동전의 합으로 X원을 만들 수 있음
  • 25원 동전이 d개 일 때, 10원 동전은 c개 만큼은 가지고 있어야 나머지 동전의 합으로 X원을 만들 수 있음
  • 위 사항을 반복

• 위 방식의 문제

  • 위의 식은 비싼 동전을 최소한으로 사용하는 방정식
  • 25원은 1,5,10원 짜리 동전과 다른 특성을 가지고 있음
  • 5원, 10원의 경우 하위 동전의 배수로 만들 수 있지만, 25원은 102 + 51 과 같은 형식으로 하위 동전이 여러 종류가 필요할 수 있음
  • 이로인해 30원을 만드는데 문제가 발생
  • 10원짜리 3개를 이용하여 30원을 만들 수 있지만(5원,1원짜리를 합쳐도 10원이 되지 않는 경우)
  • 25원 + 1원*5원을 사용할 경우 총 6개의 동전을 소모 할 수 있는 문제가 발생한다

• 위와 같은 조건이 발생할 경우 동전을 스왑하는 방식(코드1)

• 25원 동전을 d개로 고정시키지 않고 d+1개도 확인하는 방식(코드2)

# 코드 1
def solution(X:int,coins:list[int])->list[int]:
    a,b,c,d = 0,0,0,0
    # [a,b,c,d]
    # 25원 처리
    money = X-(coins[0]+5*coins[1]+10*coins[2])
    if money >0:
        d = money // 25
        if money % 25:
            d += 1
        d = min(d,coins[3])

    # 10원 처리
    money = X - (coins[0]+5*coins[1]+25*d)
    if money >0:
        c = money // 10
        if money % 10:
            c += 1
        c = min(c,coins[2])
    # 5원
    money = X - (coins[0]+10*c+25*d)
    if money >0:
        b = money // 5
        if money % 5:
            b += 1
        b = min(b,coins[1])
    # 1원
    money = X - (5*b+10*c+25*d)
    a = money
    if a > coins[0] or a<0:
        return [0,0,0,0]

    if c >= 3 and (coins[0] - a) >= 5 and (coins[3]-d)>=1:
        a,c,d = a+5,c-3,d+1
    return [a,b,c,d]

X,*coins = map(int,input().split())
ans = solution(X,coins)
print(*ans)

# 코드2
def solution(X:int,coins:list[int])->list[int]:
    a,b,c,D = 0,0,0,0
    # 25원 처리
    money = X-(coins[0]+5*coins[1]+10*coins[2])
    if money >0:
        D = money // 25
        if money % 25:
            D += 1
        D = min(D,coins[3])
    value = [0]*4
    maxCnt = 0

    for d in range(D,coins[3]+1):
        # 10원 처리
        if X - (25*d) <0:
            break
        money = X - (coins[0] + 5 * coins[1] + 25 * d)
        if money >0:
            money = X - (coins[0]+5*coins[1]+25*d)
            c = money // 10
            if money % 10:
                c += 1
            c = min(c,coins[2])
        # 5원
        money = X - (coins[0]+10*c+25*d)
        if money >0:
            b = money // 5
            if money % 5:
                b += 1
            b = min(b,coins[1])
        # 1원
        money = X - (5*b+10*c+25*d)
        a = money
        if not (a > coins[0] or a<0):
            cnt = a+b+c+d
            if maxCnt < cnt:
                maxCnt = cnt
                value = [a,b,c,d]
    if maxCnt == 0:
        return [0,0,0,0]
    return value

X,*coins = map(int,input().split())
ans = solution(X,coins)
print(*ans)