백준 1106번 호텔 JAVA

요구사항 정의

• C원을 사용하면 N명을 늘릴 수 있는 도시들 존재
• 도시들을 이용하여 C명이상의 사람들을 모으는 최소 비용을 구하기

 

제약 조건

• C <= 1000
• N <= 20
• P <= 100

 

풀이 방법

4번 넘게 틀린 문제이다.

배낭 문제와 상당히 유사하지만 새로운 유형(?)이었다.

 

변수는 cost, people이었다.

그래서 dp[i]가 의미하는 것을 정했는데 

 

처음에는 "i명의 사람이 지불하는 최소 비용"으로 생각했고 중간에 막혔다.. 

다시 풀 때는 생각을 바꿔서 "i원을 사용했을 때 얻을 수 있는 최대 사람 수"로 생각했다. 

 

dp[i] = max(dp[i], dp[i-cost] + people)

 

점화식은 다음과 같이 구성했고 특정 도시를 새로 할 것인가? 말 것인가?를 계산했다. 

 

 

이외에도 다음과 같은 문제를 겪었다.

 

- 최대 비용 계산

최대 비용을 계산하는데 어려움을 겪었다. 

내 처음 생각은 `C*N`이면 최대 비용이지 않을까? 생각했지만

정답은 `C*P` 였다.

 

최악의 경우 P원을 사용하더라도 1명밖에 안모인다면, C명을 모집하려면 `C*P`가 필요했다.

 

 

- 깨달은점

DP를 풀 때는,

• 모든 변수를 정의할 것
• dp 배열의 의미를 정의해볼 것

 

 

코드