728x90 Baekjoon1 [DP] 호텔(Python) 문제링크 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 1. 핵심 유형2-1. item을 중복해서 사용 가능 + 유형3. weight를 특정할 수 없는 경우 최소 비용을 고르기 때문에 보통은 도시(item) / 고객수(weight) / 비용(value)로 고객수 i명을 확보하기 위한 비용j라고 dp[i][j]를 정의할 수 있다. 하지만 문제는, 고객의 수, 즉 weight가 '무한'이므로 고객수를 특정할 수 없다는 것이다. 따라서 유형3으.. 2024. 2. 16. 이전 1 다음 728x90 반응형