Bibidi

1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 풀이 처음 보는 유형의 dp. dp[i]의 정의를 사람을 i명 이상 구할 때 드는 최소비용이라 정의하자. 그러면 어떤 홍보 수단이 3원에 5명을 구할 수 있다고 가정할 때 dp[i]의 최솟값은 dp[i - 5] + 3, dp[i - 4] + 3, ... , dp[i - 1] + 3 중 하나가 된다. 모든 홍보 수단에 대해 최솟값을 찾아 업데이트 하면 답을 구할 수 있다. 코드 #include using namespace std; typedef long lon..