문제
준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
예제
예제 입력 1
10 4200
1
5
10
50
100
500
1000
5000
10000
50000예제 출력 1
6예제 입력 2
10 4790
1
5
10
50
100
500
1000
5000
10000
50000예제 출력 2
12문제접근
거스름돈 문제는 그리디 알고리즘의 예제로 자주 사용되는 문제
이 문제는 입력으로 들어온 동전들을 사용하여 K원을 만드는데 필요한 동전 개수의 최솟값을 출력하는 것이 목적
예제 1의 상황
예를 들어 4200원을 최소의 동전을 이용해만면 1000원 4개 100원 2개로 총 6개가 필요함
먼저, coins안에 있는 수 중 K를 나눌 수 있는 가장 큰 수를 찾습니다. 이 예제에서는 1000이다.
그 후 K를 coin(1000)로 나눔
몫은 answer에 더해주고, 나머지는 K에 부여하면 해결가능.
answer += K // coin # 몫만큼 더하기
K %= coin # 나머지 부여
# 1. 계산대 안에 있는 돈의 수와 거슬러 줄 돈을 구합니다.
N, K = map(int, input().split()) # N : 화폐 종류수, K : 거슬러 줄 돈
# 2. 계산대에 있는 화폐들을 리스트의 형태로 입력받습니다.
coins = []
for _ in range(N):
coins.append(int(input()))
coins.sort(reverse=True)
# coins = [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]
# 3. 만약 '계산대 안에 있는 화폐'보다 '거슬러 줄 돈'이 크다면
# 돈을 거슬러 줍니다.
answer = 0
for coin in coins:
if K >= coin:
answer += K // coin 몫만큼 더하기
K %= coin 나머지 할당
if K <= 0: # 만약 K가 0이면 반복문을 탈출합니다.
break
print(answer) # 거슬러 준 동전 + 화폐의 수시간복잡도
이 코드의 시간 복잡도는 주어진 화폐의 종류 수 N과 거슬러 주어야 하는 돈 K에 선형적으로 비례합니다. 주요 연산은 화폐를 거슬러 주는 부분으로 이루어져 있습니다.
화폐를 내림차순으로 정렬하는 부분: O(N log N)
- 화폐의 종류를 정렬하는 데 걸리는 시간.
(파이썬의 내장 정렬 알고리즘은 퀵소트를 사용하므로 평균적으로 O(N log N)이 소요됩니다.)
거스름돈 계산 반복문: O(N)
- 거스름돈을 계산하고 나누고 남은 나머지를 갱신하는 부분. 최악의 경우에는 모든 화폐를 한 번씩 확인해야 하므로 O(N)
따라서 전체적인 시간 복잡도는 O(N log N) + O(N)이며,
대략적으로 O(N log N)이 됩니다.
