그리디 알고리즘2

 

퀴즈 ) 책에 있는 그리디 알고리즘으로 거스름돈 문제를 해결하려고 할 때, 반복문을 사용하지 않고 알고리즘을 구현하려면?

 

CoinChange(W)

 

입력: 거스름돈 액수 W 출력: 거스름돈 액수에 대한 최소 동전 수

 

1. change = W, n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트

 

2. if ( (change / 500) ≥ 1 ) // 입력액수가 500 이상이라 몫이 1보다 크다면

change -= 500 * (change / 500), n500 = (change / 500) // 몫의 수 * 500원 금액만큼 돈을 감소, 500원 개수 = 몫의 수

 

3. if ( (change / 100) ≥ 1 ) // 입력액수가 100 이상이라 몫이 1보다 크다면

change -= 100 * (change / 100), n100 = (change / 100) // 몫의 수 * 100원 금액만큼 돈을 감소, 100원 개수 = 몫의 수

 

4. if ( (change / 50) ≥ 1 ) // 입력액수가 50 이상이라 몫이 1보다 크다면

change -= 50 * (change / 50), n50 = (change / 50) // 몫의 수 * 50원 금액만큼 돈을 감소, 50원 개수 = 몫의 수

 

5. if ( (change / 10) ≥ 1 ) // 입력액수가 10 이상이라 몫이 1보다 크다면

change -= 10 * (change / 10), n10 = (change / 10) // 몫의 수 * 10원 금액만큼 돈을 감소, 10원 개수 = 몫의 수

 

6. if ( (change / 1) ≥ 1 ) // 입력액수가 1 이상이라 몫이 1보다 크다면

change -= 1 * (change / 1), n1 = (change / 1) // 몫의 수 * 1원 금액만큼 돈을 감소, 1원 개수 = 몫의 수

 

7. return (n500 + n100 + n50 + n10 + n1) // 총 동전 수를 리턴한다.

 

 

 

 

* 퀴즈 출처 : 4장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.