Greedy(2)_동전 알고리즘_(11047번)

작성일 | In

백준 11047

입력값: 첫째 줄에 N(동전 단위 개수), K(동전의 합)이 주어진다. 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어진다.

아이디어

리스트에 다 담아서, reverse한 이후 큰 수부터 나누어 떨어지는지 확인해서, 필요한 동전의 개수 최솟값을 구한다.

답안

T = int(input())
N, K = map(int, input().split())

arr = []
for i in range(0, N):
    a = int(input())
    arr.append(a)
arr.sort(reverse=True)

total = 0
for i in range(0, N):

    if(K >= arr[i]):
        # print("K,arr[i] :", K, arr[i])
        mod = K//arr[i]
        total += mod
        K -= mod*arr[i]
    if(K == 0):
        break
print(total)

알게된 것

  • python에는 몫을 반환하는 // 연산자가 있다
  • list 본체 정렬 함수로 a.reverse() : 리스트를 뒤집는다
  • a.sort(reverse=True)정렬,
  • a.sort(key=len)
  • list로 정렬된 결과 반환, 본체 변형 x
  • y = sorted(x)
  • y = reversed(x)

참고자료

[파이썬 리스트 정렬]https://wikidocs.net/16041

0%