[백준/Python] 11047 동전0 | 그리디(greedy)

📒 문제

---

 

 

🤸‍♀️ 문제 분석

---

원하는 k의 값을 만들기 위해 최소의 동전의 수를 구해야 하기 때문에,

💡 가지고 있는 동전 중 단위가 큰 동전부터 k로 나누어 떨어지는 동전을 연산하는 것이 유리하다. 

 

이러한 그리디 연산이 가능한 이유는 문제에 나와있는 조건인동전이 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수 이기 때문이다. 

그렇기 때문에 작은 단위의 동전으로 만들 수 있는 금액을 큰 단위의 동전으로도 반드시 만들 수 있기 때문에,

큰 단위의 동전부터 계산하는 것이 유리한 정렬 후 greedy 방식을 적용할 수 있다.

 

 

🧮코드

---

# 11047 동전0

# n : 가지고 있는 동전의 종류
# 동전의 가치의 합 = k
# 이 때 필요한 동전의 개수의 최솟값


n, k = map(int, input().split())

coins = [int(input()) for _ in range(n)]

# 내림차순 정렬
coins.sort(reverse=True)

# result : 필요한 동전의 개수
result = 0

# 동전의 종류를 하나씩 거꾸로가며
for coin in coins:
    # 구하고자 하는 k가 coin으로 나누어진다면
    if k // coin > 0:
        # 나눈 몫을 result에 더한다
        result += k // coin
        
    # 나누고 난 나머지를 k에 재할당한다
    k %= coin
    
print(result)