1. 최대점수 구하기 총시간이 주어지고 점수가 주어지고 문제를 푸는데 걸리는 시간이 주어졌을때 가장 많이 점수를 얻으려면 어떤 문제를 풀어야 하는가? 예를 들어, 아래와 같이 정보가 주어졌다고 하자 이때 1번, 2번, 4번 문제를 시간내에 풀 수 있고 이때 최대점수 41점을 얻을 수 있다. 그럼 접근 방법을 알아보자 2. 접근 방법 이전 동전문제와는 다르게 하나의 문제를 여러번 풀어서 점수를 최대화 할 수 는 없다. 그리고 20분이 한계이므로 20부터 시작해서 0으로 가는 내림차순으로 루프를 돌아야 할 것이다. 더하는 방법은 비슷하다. 다이나믹 배열에서 문제를 푸는데 걸리는 시간만큼 인덱스를 빼고 그 위치에 나온값에다가 현재 문제지의 점수를 더해서 할당하면 된다. 이것도 역시 그림으로 나타내 보았다. maxScore 결국 20분이 될

1. 동전 교환 dfs때 풀었던 알고리즘인데 동전의 갯수가 많아지고 거슬러야 할 돈이 커지면 그 유명한 stack overflow가 나게 된다. 이때 필요한게 다이나믹 알고리즘이다. 2. 접근 방법 우선 거스름돈 숫자를 길이로 하는 다이나믹 배열을 만든다. 예를 들어 20원을 바꿔줘야한다고 했을때 0부터 거스름돈 까지 바꿔줄 수 있는 경우를 순서대로 찾아간다. 이때 다음 숫자의 거스름돈은 그 전의 숫자의 거스름돈의 경우의 수에서 누적하여 계산한다. 이때 동전의 크기에서 부터 시작한다. 그리고 올라가면서 1씩 더하고 기존의 있던 값보다 작으면 할당한다. 다시 말해, 지금 1원밖에 없고 6원을 바꿔줘야하는 위치에 있으면 5원을 바꾸어줄때 발생되는 최소 동전의 갯수에다가 1을 더하면 된다. 지금 가지고 있는게 2원이고 바꿔줘야하는 돈이 6원이라면 4원을 바꾸어줄때 발생되는 최소 동전의 갯수에다가 1을 더하면 된다. 2원이고 4원을 바꿔줘야할때 [2,2] 이므로 6원은