백준 알고리즘 No.11047 동전 0

in Study #Algorithm #Python

문제

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



체감 난이도: ★

무난하게 풀린 문제..

Code

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

coin_list = [int(input()) for _ in range(n)]
coin_list.sort(reverse=True)  # 내림차순으로 정렬

coin_count = 0
for coin in coin_list:
    coin_count += k // coin   # 동전의 개수만큼 +
    k = k % coin              # 거스름돈
    
print(coin_count)

Solution

이 문제는 그리디 알고리즘을 적용해서 풀 수 있는 문제이다. coin_list를 내림차순으로 정렬하여 가장 큰 동전부터 몫을 카운트 해주면 된다. (But, 큰 동전이 작은 동전의 배수여야 한다는 조건이 있기에 사용할 수 있는 방법)

✔ Greedy Algorithm

  • 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자!
  • But, 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 때 최적이라는 보장은 없다.
  • 탐욕 선택 속성 & 최적 부분 구조 특성을 가지는 문제들을 해결하는 데 강점이 있다.

✔ List Comprehension

list를 보다 간단하게 작성할 수 있도록 지원하는 파이썬 문법

[표현식 for 항목 in iterable if 조건]
  • 표현식: 각 항목에 대한 결과 표현식
  • 항목: 반복할 대상
  • iterable: 반복 가능한 객체
  • 조건: (option) 조건식 - 특정 조건을 만족하는 경우에만 표현식을 적용

⭐️ Example

num = []
for n in range(n):
    num.append(n) 

# List Comprehension
num = [n for n in range(n)]

list 외에 set, dictionary와 같은 자료형에서 다양하게 사용 가능


혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃