[백준 파이썬]1106 호텔

[백준 파이썬]1106 호텔

https://www.acmicpc.net/problem/1106

1106번: 호텔

문제

형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

dp를 이용해서 풀었다

주어진 사람수 에 도달해야하는 문제이기에 1명부터 c명까지 도달할수 있는지 확인하고 도달한다면 현재 값보다 작은지 큰기 비교하여 작은값이 유지되도록 한다 .

 

도시 비용이 3이고 사람수는 2일때

dp[1]=max

dp[2]=3

dp[3]=max

dp[4]=6

dp[5]=max

dp[6]=9 가된다 

그리고 그다음 도시의 비용은 2이고 사람수는 3일때

dp[1]=max

dp[2]=3

dp[3]=2

dp[4]=6

dp[5]=5

dp[6]=4

 

이걸로 알수 있는게 

dp 점화식 사람수를 k라 할때  k명을 얻을수 있는 최소값을

이때 i는 사람늘리때 드는 비용 j는 늘어나는 사람수 이다 

dp[k]=min(dp[k],dp[k-j]+i)

 

이때 조건이 c가 100보다 작거나 같고 또하 적어도 c명이 늘이기 위해 라는 조건이 있기에

만약 구해야하는 사람수가 100 었을때 100일때 비용이 5이지만 105일때 비용은 4일수도 있다 그렇기에 현재 구하고 있는 사람 수만큼 100에 더해주어서 최소값을 찾는다 

 

최소값을 찾을때는 min(dp[찾는사람수:])) 를 사용하였다 이는 찾는 사람수의 인덱스부터 마지막 배열 인덱스 중 최소값을 나오게 한다 

코드

people,city=map(int,input().split())
data=[]
for i in range(city):
    v,p =map(int,input().split())
    data.append([v,p])

dp=[1e6]*(100+people)
dp[0]=0

for i,j in data:
    for k in range(1,100+people):
        if j<=k:
            dp[k]=min(dp[k],dp[k-j]+i)


print(min(dp[people:]))