dfs 로 풀려고 했으나 시간 초과로 실패
dynamic programming 을 이용하더라.
arr[i] 는 i원의 거스름돈을 주는 경우의 수이다.
money 의 각 화폐단위를 이용할 수 있는 경우의 수를 for 문을 돌면서 더해준다. 5원을 예로 들면, 1원을 만드는 경우의 수만큼 6원을 만드는 경우의 수가 추가되므로 이를 더해주는 방식.
개발블로그
dfs 로 풀려고 했으나 시간 초과로 실패
dynamic programming 을 이용하더라.
arr[i] 는 i원의 거스름돈을 주는 경우의 수이다.
money 의 각 화폐단위를 이용할 수 있는 경우의 수를 for 문을 돌면서 더해준다. 5원을 예로 들면, 1원을 만드는 경우의 수만큼 6원을 만드는 경우의 수가 추가되므로 이를 더해주는 방식.