dp #다이나믹 #다이나믹프로그래밍1 백준 14196번 : 거스름돈 2원과 5원만 가지고 거스름돈을 최소한으로 주는 방법의 수를 구하는 문제이다. 13원 = 5원 1개, 2원 4개 = 5개 14원 = 5원 2개, 2원 2개 = 2개 23원 = 거스름돈을 딱 맞게 줄 수 없으므로 -1 리턴 거스름돈을 최소한으로 주기 위해서는 5원짜리로 최대한 많이 주어야만 한다. 그렇기 때문에, 5원을 최대한으로 주었을 때를 가장 먼저 계산해야 한다. 1. 거스름돈이 n이라 할때, 일단 n/5를 통해 가장 많이 줄 수 있는 5원의 개수를 구한다. 2. 1번에서 값이 딱 떨어진다면, 5원으로만 거스름돈을 줄 수 있기 때문에 해당 값이 최솟값일 것이다. 하지만, 여기에서 값이 떨어지지 않았다면 5원을 주고 남은 나머지 금액을 2원으로 줄 수 있는지 확인한다. 나머지가 모두 2원으로 떨어진다면.. 2021. 2. 23. 이전 1 다음
