만두 지불 및 지갑 다이어트

요 전날 낮에 회사 이웃에서 만두 정식을 먹으러 갔습니다. 타마치에는 만두 정식을 먹을 수 있는 곳이 몇 군데 있습니다만, 그 날 갔던 곳의 만두는 한층 크고, 충분히 고기가 가득 있어 먹고 먹을 수 있는 점에서 마음에 들고 있어, 달에 1회의 페이스로 먹으러 가고 있습니다.

그런데, 먹고 끝내, 평소부터 함께 점심하고 있는 동료와 한가지의 잡담을 하고 나서 회계에 갔던 곳으로부터가 본제가 됩니다.

여기서 여러분, 정식의 가격이 880엔이라는 깔끔한 설정이었을 경우, 지갑에서 내는 동전은 어떻게 선택합니까?

나는 그 때 평소의 습관에서 「400엔…」이라고 말하면서, 지갑에 있던 100엔을 4장과 현금 트레이에 배치해, 마지막에 천엔 지폐를 동전 옆에 붙이도록(듯이) 냈습니다 . (100엔보다 작은 동전이 없었기 때문입니다.)

점주로부터 받은 낚시의 520엔을 지갑에 버리고 가게를 나온 후, 동료로부터와 어떤 사실을 알았습니다.

언제부터 지갑에 모이는 동전의 매수를 최소한으로 유지하기 위해 하고 있는 습관입니다만, 이렇게 880엔의 회계를 할 때에 1400엔을 낸다는 것은 세간적으로는 드물다는 것 입니다.

여러분도 스스로는 무심코 습관으로 하고 있는 것이, 주위의 사람으로부터 말해 처음으로 그렇지 않다고 깨달은 것이 있는 것은 아닐까요. 그 때의 순간이나 다른 사람의 습관이 알려질 때는 의미심장하네요.

끝.

P.S. 이것만이라면 기술계의 투고가 되지 않기 때문에, 지갑의 동전을 최저 매수로 유지하는 방법의 로직을 생각해 보기로 했습니다.

지불 로직화

의외로 어려웠다···결론으로부터 말하면, 아래와 같이 조금 생각했지만, 좋은 방법이 조금 살짝으로 생각해 버릴 것 같지 않기 때문에 포기했습니다.

일본이라면 1000엔이나 10000엔 등과 같이 백십일 정도가 0인 지폐가 있으므로 거기에 맞추어 조합 선택하고 있지만, 어떤 동전·지폐의 종류가 있는 나라에도 대응할 수 있는 범용적인 로직은 좋은 생각이 들지 않는다 ...

어쨌든 일본 통화의 정의는 이런 것

denominations = [1, 5, 10, 50, 100, 500, 1000, 10000]

알고리즘 1：지갑의 내용을 아무것도 생각하지 않고 전부 건네주고 그것에 대해서 어선을 계산해 주고, 돌아온 낚시로부터 원래 건네지 않아도 좋았던 통화·지폐를 당긴다

최적의 어선을 요구하는 처리는 어쩔 수 없이 쓸 수 있다(현금 드로어안은 무한이라고 하는 전제)

def denomiate_amount(amount):
    denominated = {}
    for denomination in reversed(sorted(denominations)):
        denominated[denomination] = int(amount / denomination) * denomination
        amount -= denominated[denomination] 
    return denominated

지갑에 100 엔이 4 장과 천엔이 1 장 있을 때

wallet = {100: 4, 1000: 1}

880 엔 식사를 한 경우

# 買い上げ額
price = 880

# お財布そのまま出す
tray = wallet

# お釣りの額を計算
change = sum(d * n for d, n in tray.items()) - price
if change < 0:
    raise # 足りない

# 釣銭の最適な組み合わせ
changed = denomiate_amount(change)

# 戻ってきた硬貨を引いた組み合わせ
optimal = {d: n - changed[d] for d, n in wallet.items()}

라는 느낌으로 optimal 에 결과가 구해진다.

다만, 잡잡한 로직이기 때문에 문제가 곧바로 하나 생각된다:

지갑 안에 원래 천엔 지폐가 11장 있었던 경우, 11,400엔을 내고 1만엔 지폐와 520엔의 낚시를 받지만, 천엔 11매와 1만엔 지폐는 상쇄되지 않기 때문에, 실제로 그것을 내게 된다. 이것은 가게에 상당한 괴롭힘이라고 생각한다 ...

안쪽이 깊을 것 같기 때문에 이 근처에서 수상으로 합니다.

깨끗한 알고리즘이 떠오른 분은 꼭 코멘트를 주세요.