devbelly

문제 www.acmicpc.net/problem/2720 알고리즘 구현 풀이 이 문제는 제가 파이썬 구현 연습을 위해 풀다가 마주한 문제입니다. 구현 외에 짚고 넘어갈 점이 있어 포스팅하겠습니다. 저는 브론즈3이라는 점에서 구현 외에 별 다른 부분은 신경쓰지 않고 풀었던 문제입니다. 하지만 조금 생각해본다면 수상한 점을 발견할 수 있습니다. 문제 내용은 거슬러 주는 동전의 갯수를 최소화 하는 문제입니다. 그리디 또는 다이나믹 프로그래밍을 다룰 때 많이 등장하는 주제중 하나입니다. 그리디로 문제를 해결하려고 동전의 값을 보았지만 거슬러 줄 수 있는 동전의 값은 25원 10원 5원 1원 입니다. 동전들 끼리 배수관계를 만족하지 못하므로 (25원과 10원) 다이나믹 프로그래밍을 이용해 해결하자! 라고 생각할 ..