[이코테] 그리디_거스름돈(자바스크립트)

이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

---

문제

입력

1260
500 100 50 10

출력

6

---

정답 코드

답안1

답안2

---

문제 풀이

 나는 while 반복문을 통해 주어진 돈에서 가장 큰 단위 동전부터 차례대로 빼나가고, 작업을 수행할 때마다 cnt를 1씩 증가시켰다. 이때 돈이 현재 동전보다 작아진다면 인덱스를 증가시켜 동전 종류를 바꾸는 식으로 풀었다.

 해답의 경우 풀이가 더 간단하다. 우선 cnt에는 주어진 돈에 동전을 나눈 몫을 누적시킨다. 그리고 해당 돈을 동전으로 나눴을 때의 나머지로 기존의 돈을 치환한다. 즉 다음과 같이 계산이 수행되는 것이다.

현재 동전: 500
동전 개수: 2
돈 변화 추이: 260

현재 동전: 100
동전 개수: 4
돈 변화 추이: 60

현재 동전: 50
동전 개수: 5
돈 변화 추이: 10

현재 동전: 10
동전 개수: 6
돈 변화 추이: 0