목록동적 계획 알고리즘 (1)

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

[백준 14916] 거스름돈 파이썬 문제 풀이

문제 풀이: 해당 문제는 동적 계획 알고리즘을 이용해서 풀면 된다. 거스름돈을 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..
Python/백준 문제풀이 2023. 6. 29. 16:26
이전 Prev 1 Next 다음