알고리즘 선택 트랙 [3일차]

<문제>

백준 11047문제

동전0

 

<풀이 회고>

일단 이 문제를 보았을 때는 최솟값,최댓값등 극단적인 상황을 물어보고 있기 때문에 그리디 알고리즘으로 보았다.

그럼 일단 그리디 알고리즘에 대해 간단하게 설명하겠다.

그리디 알고리즘은 상황을 극단적으로 몰고 가서 가장 간단한 해법을 도출하는 방법이다.

그럼 가장 간단한 해법을 도출해보겠다!!

1. 알고리즘

 

여기서 핵심이 되는 알고리즘은 바로 동전 리스트를 내림차순으로 배치하는 것이다.

즉 동전 리스트에 원소들을 큰거부터 비교를 하면서 만약 동전값과 주어진 수를 비교하는 작업을 하면 됩니다!

2. 구현

N, K = map(int,input().split()) # 입력 받기
coins = [None] * N
cnt = 0

for i in range(N, 0, -1):
    coins[i-1] = int(input()) # 동전의 가치를 입력 받기

for i in range(0, N, 1):
    if coins[i] <= K:
        cnt += K // coins[i]
        K %= coins[i]
print(cnt)

3. 결론

결국 그리디 알고리즘은 가장 짧고 간단하게 살펴봐야한다!!!!!!