백준 1106번: 호텔

백준 1106번: 호텔

이번에는 dp 문제이다. dp문제는 풀어도 풀어도 어려워서.. 어렵지 않은 것 같은데 계속 틀려서 한참동안 삽질을 하다가 다른 분들의 풀이를 보고 해결할 수 있었다.

C, N = map(int,input().split())
graph=[list(map(int,input().split())) for _ in range(N)]
dp=[float('INF') for _ in range(C+100)]
dp[0] =0
for fee,num in graph:
    for i in range(num, C+100):
        dp[i] = min(dp[i-num]+fee, dp[i])

print(min(dp[C:]))

코드이다. 해당 dp[i] = min(dp[i-num]+fee, dp[i])는 i=num일때부터를 시작해서, dp[i-num]의 값이 INF값이 아닐때, 즉 정수배가 되는 기준 데이터가 존재할때 채워지게 된다. 예를들어 3의 비용을 지불할때 5만큼 관광객이 증가한다고 하자. 그러면 dp[5]=3, dp[6]=INF, ... , dp[10]=6(dp[5]+3)... 이런식으로 정수배에 대해서 값이 채워질 것이다. 이 다음에 1의 비용을 지불할때 1만큼 증가한다고 하자. 그러면 dp[1]=1, dp[2]=2, ... , dp[5]=min(3,5)=3이 되는 것이다. 즉, N명의 고객의 유치하기 위해 드는 최소 비용을 계산한다.

나는 풀이할때 반대로 N만큼의 금액으로 유치할 수 있는 최대 고객수를 구하고, 이 고객수가 C보다 크면 출력하는 걸로, 그러니까 반대로 dp를 만들어서 접근했어서 이 방식으로는 어떻게 풀이해야할지 고민했는데 이렇게했을 때 맞는 풀이는 아래와 같다.

C, N = map(int,input().split())
graph = []
max_val = 0
for _ in range(N):
    fee, num = map(int,input().split())
    graph.append([fee,num])
    max_val = max(max_val,C*fee)
dp=[0 for _ in range(max_val+1)]

for fee,num in graph:
    for i in range(fee,len(dp)):
        dp[i]=max(dp[i-fee]+num,dp[i])

for i in range(len(dp)):
    if dp[i]>=C:
        print(i)
        break

아무래도 전체 dp크기 구하기가 어려워서 (C*fee는 넉넉하게 잡은 크기다.. 정확한 추산방법은 잘 모르겠다.) 이 방법보단 위의 방법으로 푸는게 더 간결할 것 같음. 어차피 들어오는 입력값을 기준으로 계산할 수 있는 숫자에 대해서만 계산하게 되니까 공식자체에는 큰 차이가 없다.