Greedy

from functools import lru_cache


def valid_coins(amount, coins):
    if type(amount) is not int or amount < 0:
        raise ValueError("amount must be a nonnegative integer")
    if any(type(coin) is not int or coin <= 0 for coin in coins):
        raise ValueError("coins must be positive integers")
    return sorted(set(coins), reverse=True)


def greedy_coins(amount, coins):
    coins = valid_coins(amount, coins)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count if amount == 0 else None


def min_coins_dp(amount, coins):
    coins = valid_coins(amount, coins)
    unreachable = amount + 1
    best = [0] + [unreachable] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value:
                best[value] = min(best[value], 1 + best[value - coin])
    return None if best[amount] == unreachable else best[amount]


def min_unplugs(capacity, schedule, events=None):
    if type(capacity) is not int or capacity < 1:
        raise ValueError("capacity must be a positive integer")
    plugged = []
    count = 0
    for i, device in enumerate(schedule):
        if device in plugged:
            continue
        if len(plugged) < capacity:
            plugged.append(device)
            continue
        farthest, target = -1, None
        for old in plugged:
            try:
                next_use = schedule.index(old, i + 1)
            except ValueError:
                target = old
                break
            if next_use > farthest:
                farthest, target = next_use, old
        plugged.remove(target)
        plugged.append(device)
        count += 1
        if events is not None:
            events.append((i, target, device))
    return count


# 작은 일정에서는 가능한 제거 대상을 모두 비교해 Greedy의 답을 확인한다.
def optimal_unplugs(capacity, schedule):
    @lru_cache(None)
    def solve(i, state):
        if i == len(schedule):
            return 0
        device = schedule[i]
        plugged = set(state)
        if device in plugged:
            return solve(i + 1, state)
        if len(plugged) < capacity:
            return solve(i + 1, tuple(sorted(plugged | {device})))
        return 1 + min(solve(i + 1, tuple(sorted((plugged - {old}) | {device})))
                       for old in plugged)
    return solve(0, ())


def main():
    for amount, coins, greedy_answer, optimum in [
        (1320, [500, 100, 50, 10], 7, 7),
        (6, [4, 3, 1], 3, 2),
        (6, [4, 3], None, 2),
        (5, [4, 2], None, None),
        (0, [], 0, 0),
    ]:
        assert greedy_coins(amount, coins) == greedy_answer
        assert min_coins_dp(amount, coins) == optimum
        print(f"coins {coins}, amount={amount}: greedy={greedy_answer}; optimum={optimum}")
    for amount, coins in [(-1, [1]), (3, [0]), (3, [-1])]:
        for function in (greedy_coins, min_coins_dp):
            try:
                function(amount, coins)
            except ValueError:
                pass
            else:
                raise AssertionError("invalid coin input was accepted")

    schedule = [2, 3, 2, 3, 1, 2, 7]
    events = []
    assert min_unplugs(2, schedule, events) == optimal_unplugs(2, schedule) == 2
    assert events == [(4, 3, 1), (6, 2, 7)]
    print(f"schedule sample: unplugs=2; events={events}")
    schedules = [[], [1], [1, 1, 1], [1, 2, 3], [1, 2, 3, 1, 2, 3],
                 [1, 2, 1, 3, 2, 4, 1], [1, 2, 3, 4, 3, 2, 1]]
    for sequence in schedules:
        for capacity in (1, 2, 3):
            before = sequence[:]
            assert min_unplugs(capacity, sequence) == optimal_unplugs(capacity, sequence)
            assert sequence == before
    try:
        min_unplugs(0, [1])
    except ValueError:
        pass
    else:
        raise AssertionError("zero capacity was accepted")
    print("21 small schedule cases: matched exhaustive choices")
    print("invalid inputs: rejected; all checks passed")


if __name__ == "__main__":
    main()

coins [500, 100, 50, 10], amount=1320: greedy=7; optimum=7
coins [4, 3, 1], amount=6: greedy=3; optimum=2
coins [4, 3], amount=6: greedy=None; optimum=2
coins [4, 2], amount=5: greedy=None; optimum=None
coins [], amount=0: greedy=0; optimum=0
schedule sample: unplugs=2; events=[(4, 3, 1), (6, 2, 7)]
21 small schedule cases: matched exhaustive choices
invalid inputs: rejected; all checks passed