032 동전 0

첫번째 코드

 

그리디 알고리즘에 대해서 배우고 처음 푼 문제이다!

그리디 알고리즘 자체는 어렵지 않고 코드를 짤때도 어려움이 없었다.

아이디어는 책을 참고했으나 책의 아이디어를 바탕으로 코드를 작성했는데 거의 똑같은 것을 보아 아주 잘 이해했구만!

근데 앞으로 아이디어를 만들어 내는 것이 관건일 것 같다..ㄷㄷ

 

먼저 sorting 되어 있는 동전 기준으로 가질 수 있는 가장 큰 동전을 가져와서 k에서 나눈 값의 몫만큼 count에 더해준다.

그리고 나머지를 k로 갱신하고 위와 같은 방법으로 계속 진행한다.

 

n, k = map(int, input().split())
A = []
count = 0

for _ in range(n):
    A.append(int(input()))

for i in range(n-1, -1, -1):
    if A[i] <= k:
        count += (k // A[i])
        k = (k % A[i])

print(count)

 

통과!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11047.%E2%80%85%EB%8F%99%EC%A0%84%E2%80%850

programmers/백준/Silver/11047. 동전 0 at main · ornni/programmers