tose33

https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 배낭 문제인데 약간의 변형이 있다. 기본적으로 배낭 문제의 점화식은 거의 다음과 같다 d[i][j] = max(d[i-1][j], d[i-1][j-cost[i]] + people[i]) 즉 i번째 요소를 선택할지 안할지 아니면 i-1번째 까지 계산한 값을 유지할지다. 그런데 이 문제는 (3, 5) 가 주어지면 3원으로 5명의 고객을 유치 가능한데 여기에 더해서 6원으로 10명, 9원으로 15명..