주니어로서의 백 걸음, 개발자로서의 한 걸음

문제 풀이: 해당 문제는 동적 계획 알고리즘을 이용해서 풀면 된다. 거스름돈을 1원부터 총거스름돈의 액수까지 1씩 증가시키고 각각의 상황에서 2원과 5원을 썼을 때 거스름돈이 최소인 경우를 구하고 거슬러 줄 수 없으면 -1을 출력하면 된다. 예를 들어 거스름돈이 13원인 경우를 보자 처음에 2원짜리 동전을 사용하면 동전을 다 거슬러주지 못하는 상황이 발생한다. 다음으로 5원을 사용하는 경우, 이전에 거스름돈이 8원이었을 때(c [13-5] = c [8], c [8] = 4), 2원짜리 동전 4개 사용됨. 여기에 5원짜리 동전 한 개를 추가하면 13원이 된다. money = int(input()) m = [2, 5] max = 1000000 c = [max] * (money + 1) c[0] = 0 for..

문제 풀이: 가장 큰 화폐단위부터 비교하며 액수가 큰 화폐를 최대한 많이 사용하면 된다. n = int(input()) c = 1000 - n cnt = 0 m = [500, 100, 50, 10, 5, 1] for i in m: if c == 0: break cnt += c // i c %= i print(cnt)