10. DP 연습 - Resource Allocation Problem (자원 할당 문제)

1. 개요

자원 할당 문제는 DP방식으로 풀이하는 아주 유용한 방법.

N개 대상에게 M개 자원을 할당할 때, 주어진 각각의 0부터 N-1개 대상이 M자원의 개수에 따라 얻을 수 있는

수익을 가진 데이터를 입력하면 최대 수익을 가지는 데이터를 보내준다.

흔히, 여러 기업에 투자했을 때, 얻을 수 있는 최대 수익을 뜻한다.

<점화식>

N번째 대상까지 M개의 자원을 투자했을 때, 최대 수익은

이번(N)대상에게 자원 0할당 + 나머지 대상에게 자원 M-0할당

이번(N)대상에게 자원 1할당 + 나머지 대상에게 자원 M-1할당

이번(N)대상에게 자원 2할당 + 나머지 대상에게 자원 M-2할당

.......

이번(N)대상에게 자원 Limit할당 + 나머지 대상에게 자원 M-M할당

중에서 최대값이다.

이 문제를 통해서 드디어 DP의 비밀을 벗겨냈다. 점점 자신감이 차오른다.

이젠 라이브러리 사용 숙달과 시간 제한이 있을 때, 평정심만 잃지말자.

평정심을 잃었을 때, 코드를 짜는 것은

지도를 보지 않고 전략을 짜는 것과 다를 바가 없다.

2. 문제

N개 대상에 M개의 자원을 할당했을 때 최대가 되는 자원 할당 값을 구하시오.

(예시)

3개의 기업에 0만원부터 4만원까지 투자했을 때, 최대가 되는 수익을 뜻함.

투자를 하지 않으면, 수익도 없음.

3. 전체코드 및 출력

3-1) 전체코드

3-2) 출력

<여기서 출력값이 다른 이유는 재귀는 모든 과정을 따라잡기 때문에 4만원 투자보다 3만원을 투자했을 때, 

훨씬 더 큰 수익이 나는 것을 알아서 29만원을 추출한 것이다. 9+10+10. 하지만 DP는 정확히 4만원일 때의

최대값을 추출한 것으로 7+10+10해서 27이다. 결론은 자원 소모에 따라 수익도 늘어나야 하는데 랜덤으로

데이터를 추출해서 이런 경우가 생긴다. 문제될 것은 없다. 물론 DP역시 재귀처럼 구하려면 할 수 있다.>