본문 바로가기

Algorithm/Baekjoon

Baekjoon #11047 - 동전 0

목차

1. 문제

2. 입출력 예시

3. 문제 풀이

1. 문제

2. 입출력 예시

입력 예시 출력 예시
10 4200 1 5 10 50 100 500 1000 5000 10000 50000 6
10 4790 1 5 10 50 100 500 1000 5000 10000 50000 12

3. 문제 풀이

이 문제 역시 굉장히 간단했다. 이를 해결하기 위한 순서는 다음과 같다.

  1. 동전 종류의 수량(N)과 가치의 합(K)를 입력받는다.
  2. 동전의 가치가 담긴 정보(A)를 입력받는다.
  3. 동전의 가치는 오름차순으로 주어지므로, 이를 내림차순으로 정렬한다.
  4. 반복문을 통해 동전의 가치가 담긴 리스트를 반복하며, 가치의 합에 동전 가치를 나눈 몫을 동전 수량에 더해준다. 그리고 가치의 합은 가치의 합에 동전 가치를 나눈 나머지로 적용한다.
  5. 가치의 합을 맞추기 위한 동전의 수량을 출력한다.

이를 코드로 나타내면 아래와 같다.

def solution(k, a):
    a.sort(reverse=True)

    cnt = 0

    for i in a:
        cnt += k // i
        k %= i

    print(cnt)


N, K = [int(x) for x in input().split(" ")]
A = [int(input()) for x in range(N)]

solution(K, A)

위 코드의 메모리는 28,776 KB, 시간은 84 ms가 소요되었다.

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon #1541 - 잃어버린 괄호  (0) 2021.03.22
Baekjoon #5585 - 거스름돈  (0) 2021.03.21
Baekjoon #1931 - 회의실 배정  (0) 2021.03.21
Baekjoon #11399 - ATM  (0) 2021.03.20
Baekjoon #2839 - 설탕 배달  (0) 2021.03.20