[백준-11047(그리디)] 동전 0

문제 바로가기

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력

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

---

핵심 아이디어: 그리디 알고리즘(Greedy)

 

탐욕적 선택 기준

가장 가치가 큰 동전부터 가능한 만큼 사용하면, 전체 동전 개수를 줄일 수 있음.
즉, 지금 상황에서 가장 큰 값을 우선적으로 선택하는 것 이 문제를 가장 효율적으로 푸는 열쇠입니다.

 

왜 그리디가 가능한가?

문제에 등장하는 동전들은 항상 배수로 구성된 것은 아니지만, 단조 증가하고 모든 가치가 정수이므로
큰 동전부터 차감하면서 구성해도 최소 개수를 보장할 수 있음 (문제 조건이 그리디 조건을 만족함)

 

접근 방법 (전략)

1. 동전 배열을 내림차순으로 정렬 (큰 가치부터)
2. 현재 목표 금액 K보다 작거나 같은 동전을 최대한 많이 사용
3. 그만큼 K에서 차감
4. 이를 반복하며 사용한 동전 개수를 누적
5. K가 0이 되면 종료

# 동전 종류의 수 n, 목표 금액 k 입력
n, k = map(int, input().split())

# n개의 동전 가치를 리스트로 입력받음
coins = [int(input()) for _ in range(n)]

# 큰 동전부터 사용하기 위해 내림차순 정렬
coins.sort(reverse=True)

# 동전 개수를 누적할 변수 초기화
count = 0

# 큰 동전부터 하나씩 확인하면서
for coin in coins:
    # 현재 동전이 목표 금액보다 작거나 같으면
    if k >= coin:
        # 해당 동전을 최대 몇 개 사용할 수 있는지 계산
        count += k // coin
        # 해당 동전만큼 금액에서 차감
        k %= coin

# 최소 동전 개수 출력
print(count)