[BOJ] [Python] 11047번 : 동전 0

먼저, 동전 N종류를 내림차순으로 정렬해 리스트에 저장한다.

 

리스트 0번째부터 n-1번째까지 k원을 리스트의 각 값으로 나눈다.

각 나누는 과정이 끝날 때마다 나머지 값으로 K원을 갱신한다.

 

K원보다 리스트의 값이 크다면, K원은 변하지 않을 것이다.

이는 동전을 사용하지 않았다는 뜻이 된다.

 

따라서, K원보다 작거나 같을 때를 따로 체크해서 동전을 사용했음을 확인해야 한다.

 

 

num = list(map(int, input().split()))

kind = num[0]
target = num[1]

wallet = []

for _ in range(kind):
    wallet.append(int(input()))

wallet.reverse()
result = 0

for coin in wallet:
    if coin <= target:
        result += target // coin
    target %= coin

    if target == 0:
        print(result)
        break

 

 

 

 

 

처음에는 이진 탐색으로 풀려고 했다.

 

왜냐하면, K원과 가장 가까운 작은 값을 찾고, 그 수부터 K원을 나누면 될 것 같았기 때문이다.

 

하지만 계속 "틀렸습니다"가 나왔고, 위 코드로 다시 구현하면서 굳이 이진 탐색을 쓸 필요가 없다는 걸 느꼈다.

 

 

num = list(map(int, input().split()))

kind = num[0]
target_i = num[1]

wallet_i = []

for _ in range(kind):
    wallet_i.append(int(input()))

c = 0


def BSearch(wallet, target, count):
    low = 0
    high = len(wallet) - 1

    result = 0

    if target == 0:
        print(count)
        return count

    else:
        while low <= high:
            mid = (low + high) // 2

            if wallet[mid] < target:
                result = mid
                low = mid + 1

            else:
                high = mid - 1

        if wallet[result] <= target:

            count += target // wallet[result]
            target = target % wallet[result]

            BSearch(wallet, target, count)

        else:
            print(0)
            return 0


BSearch(wallet_i, target_i, c)