11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
그리디 알고리즘(Greedy)
: 가장 최선의 선택을 하는 기법
처음에 최선의 선택을 한 것이 최후에도 가장 최선의 선택이길 바라는 알고리즘
따라서, 모든 경우에서 그리디 알고리즘이 통하는 것이 아니다.
#동전 0
n, k = map(int, input().split(' '))
coin = []
for i in range(n):
coin.append(int(input())) #오름차순으로 동전 n개 받기
coin = coin[::-1]
a = 0
for i in range(len(coin)): #가장 큰 돈부터 작은 돈까지
if coin[i] <= k: #k보다 작아야함
a += k//coin[i] #동전 개수
b = k%coin[i] #남은 돈
k = b
if k == 0:
break
print(a)처음으로 풀어본 그리디 알고리즘 관련 문제였었다. 당시에 그리디가뭔데!?하면서 뭔지 읽어봐도 그래서 뭐냐구! 했던거로 기억하는데,, 실제로 이 문제를 풀면서 어떤 알고리즘인지 감을 잡게 되었었다.
모든 경우에서 그리디 알고리즘이 통하지 않는다라는 부분은 주어진 예시가 모두 규칙적으로 50, 1000, 50000이런 식으로 주어져 있는데, 만약 300과 같은 동전이 주어진 경우에는 값이 달라지는 경우가 생기므로 통하지 않는다..
(안정확할 수도 있는데.. 다른 방법을 쓰는 게 낫지 않나..라는 생각이 드는데,, 좀더 공부를 해봐야겠다!ㅎ)
반응형