총시간이 주어지고 점수가 주어지고 문제를 푸는데 걸리는 시간이 주어졌을때 가장 많이 점수를 얻으려면 어떤 문제를 풀어야 하는가?예를 들어, 아래와 같이 정보가 주어졌다고 하자이때 1번, 2번, 4번 문제를 시간내에 풀 수 있고 이때 최대점수 41점을 얻을 수 있다.그럼
dfs때 풀었던 알고리즘인데 동전의 갯수가 많아지고 거슬러야 할 돈이 커지면 그 유명한 stack overflow가 나게 된다. 이때 필요한게 다이나믹 알고리즘이다.우선 거스름돈 숫자를 길이로 하는 다이나믹 배열을 만든다. 예를 들어 20원을 바꿔줘야한다고 했을때 0부