그리디 알고리즘(탐욕 알고리즘) #백준 11047

그리디 알고리즘이란?

현재 시점에서 최적의 답을 찾기 위한 선택을 하는 방법입니다. 가장 직관적인 문제해결이지만 제한 조건을 만족하는 적합한 해를 찾는 방법이지 최적의 해를 찾는 방법은 아닙니다. 최적의 해를 찾기 위해서는 동적계획법(Dynamic Programming)을 사용합니다.

 

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

[ 문제 해결 과정 ]

각각의 동전은 매우 많고 동전은 N종류가 있고 주어진 값에서 최소한의 동전으로 그 값을 표현하여야 한다.최소한을 물어보므로 그리디 알고리즘을 생각했다. 그리고 주어진 K값을 동전중 큰 순으로 나누다 보면 최소한의 동전을 구할 수 있을 것이다

 

[ 소스코드 ]

#동전과 값 입력받기
n,k=map(int,input().split())
#동전을 입력받을 리스트 초기화하기
coin=[]

#동전 종류 입력받기
for i in range(n):
  coin.append(int(input()))

#동전개수 셀 변수 초기화
result=0

#동전 내림차순으로 정렬하기
coin.sort(reverse=True)

#동전 개수 구하기
for i in coin:
  if k==0: break
  result+=k//i
  k%=i
  

print(result)