목록그리디 (1)
우당탕탕 개발일지
[알고리즘] 그리디 알고리즘 실전문제1: 거스름돈 문제
문제상황 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 있다고 가정. 거스름돈이 N원일 때 거슬러줘야 하는 동전의 최소 개수를 구하라. 변수 설정 변수 설명 N 거스름돈 count 거슬러줘야 하는 동전의 최소 개수 k 동전의 종류 수 풀이 전략 거슬러줘야 하는 동전을 최소화하기 위해서는 크기가 큰 500원을 최대로, 그 다음에는 100원을 최대로 ... 사용해야 한다. 일단 N을 500으로 나누었을 때, 몫은 '필요한 500원 동전의 개수'에 해당한다. 그 나머지를 100으로 나누었을 때, 몫은 '필요한 100원 동전의 개수'에 해당한다. ... 이 과정을 10원짜리 동전까지 진행하는 코드는 다음과 같다. N = 1260 count = 0 list = [500, 100, 50..
알고리즘
2023. 9. 26. 16:39