백준(Baekjoon Online Judge) - 11047번(동전 0) 문제 풀이

1. 문제

2. 입출력 예시

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가 소요되었다.

참고자료

• 백준알고리즘 문제 - 11047번 동전 0