[BOJ/python]1106번 호텔, knapsack 알고리즘 설명

냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다.

1106번 문제를 풀기 전에 1차원 배열을 이용해 평범한 배낭 문제를 풀이하는 방법을 알아보자.

0. 일반적인 냅색 문제 풀이(1차원 / 2차원 배열 이용)

12865번 평범한 배낭 문제를 기준으로 설명하겠습니다. https://www.acmicpc.net/problem/12865

2차원 배열에서 dp[i][j]에 i번째 보석까지 j 무게를 사용했을 때 얻을 수 있는 최대 가치를 저장한다. 모든 보석에 대하여 1에서 최대 용량까지 반복문을 실행하며 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+ benefit)로 갱신한다.

2차원 배열을 사용하여 bottom-up 방식으로 풀지 않고 1차원 배열을 이용하여 top-down 방식으로 냅색 문제를 해결할 수도 있다.

1차원 배열에서는 dp[k]에는 k 무게를 사용했을 때 최대 가치를 저장한다. 모든 보석에 대하여 가방의 최대 용량부터 1까지 반복문을 실행하며 dp[k] = max(dp[k], dp[k-cost] + benefit)로 갱신한다.

 

1차원 배열을 이용할 때는

 

• 가방에 담는 보석의 종류를 늘려가며
• 가능한 무게 범위를 1부터 최대 용량까지 늘려가며
• 현재 보석을 넣는 것이 이득인지 이전의 보석까지만 사용하는 것이 이득인지를 비교하며
• 최종적으로 모든 보석을 사용한 경우에 최대 가치를 구한다.

 

2차원 배열을 이용할 때는

 

• 가방에 담는 보석의 종류를 늘려가며
• 가방의 무게 범위를 최대 용량에서 1까지 탐색하며
• 이전 단계에서 보석을 사용하여 얻은 최대 가치와 현재 보석 1개를 추가 사용하는 경우 최대 가치 비교하며
• 최종적으로 모든 보석을 사용한 경우 최대 가치를 구한다.

 

가장 핵심은 최대 용량부터 거꾸로 반복문을 실행해야 각각의 보석을 1개만 사용하게 된다.

첫번째 보석을 넣는 경우를 생각해보자. 만약 1부터 최대 용량까지 반복문을 실행하며 dp를 갱신하면 dp[k-cost] + benefit 에서 dp[k-cost]에는 이미 첫번째 보석을 사용했을 때의 최대 가치가 저장되어 있다.

그러므로 최대 용량 부터 거꾸로 반복문을 실행하여 i번째 보석을 사용하지 않고 i-1번째 보석을 사용했을 때 최대 가치와 현재 보석을 1개를 추가적으로 사용했을 때 최대 가치를 비교 후 갱신을 해주는 것이다.

즉, 1차원 dp의 경우 몇 번째 보석까지 사용했는지는 dp에 표시하지 않고 거꾸로 반복문을 실행하는 것 자체로 표현할 수 있다.

1. 1106번 2차원 배열을 이용한 풀이

이제 1106번 문제를 풀어보자.

1-1. 알고리즘 설명

각 도시에는 비용과 그에 따른 이득이 정해져있다. 각 도시에 여러 번 투자할 수 있다. 냅색 문제에 비유해보자면 각 종류의 보석을 여러 번 가방에 담을 수 있는 문제다. 최소 C의 이득을 보기 위해 필요한 최소 비용을 구해야 한다.

 

• dp[i][j] = i번째 도시까지 선택하여 적어도 j이득을 보기 위한 최소 비용
• dp[i][j] = min(dp[i-1][j-benefit] + cost, dp[i-1][j])

 

만약 각 도시를 한 번씩만 선택할 수 있다면, 현재 도시의 이득이 benefit, 비용은 cost일 때 i번째 도시까지 선택했을 때 j이득을 보기 위한 최소 비용은 i-1번째 도시까지 선택했을 때 j-benefit 이득을 보기 위한 최소 비용 + cost 혹은 i-1번째 도시까지 선택했을 때 j 이득을 보기 위한 최소 비용 중 더 작은 값으로 갱신하면 된다.

그러나 해당 문제는 같은 도시를 여러 번 선택할 수 있으므로, 반복문을 통해 dp[i-1][j-benefit] + cost, dp[i-1][j-2benefit] + 2cost, ..., dp[i-1][j-kbenefit] + kcost 중 가장 작은 값으로 갱신한다.

이 때 j-k*benefit가 0보다 작아지면 반복문을 중단한다. 다만 0보다 작아지는 시점에는 dp[i][j]를 현재 도시만 선택한 경우, 즉 *kcost와 dp[i-1][j]만 비교해준다.

1-2. 코드 설명

1. 루프를 반복하며 dp에는 최소 비용이 갱신되므로 inf 값으로 초기화 해준다.
2. 모든 도시에 대하여 1부터 C까지 이중 반복문을 실행한다.
3. k의 값을 1씩 늘려가며 현재 도시를 가능한 여러 번 선택한 경우를 모두 탐색한다.
4. j-(k*benefit) <=0 인 경우에 갱신하고 무한 루프를 중단시킨다.

1-3. 코드

#호텔
C, N = map(int, input().split())
hotel=[[0,0]] #cost, benefit, Benefit per Cost

maxCost = float('INF')

for i in range(N):
    line= list(map(int, input().split()))
    hotel.append(line)

dp = [ [ maxCost for _ in range(C+1)] for _ in range(N+1) ]

for i in range(1,N+1):
    benefit = hotel[i][1]
    cost = hotel[i][0]
    
    for j in range(1, C+1):
        
        dp[i][j] = dp[i-1][j]
        
        k=0
        while True:
            if j-(k*benefit) <=0 :
                dp[i][j] = min(dp[i][j], k*cost)
                break
            
            else:
                dp[i][j] = min(dp[i][j], dp[i-1][j-k*benefit] + k*cost)
            k+=1
             
print(dp[N][-1])

2. 1106번 1차원 배열을 이용한 풀이

2-1. 알고리즘 설명

1차원 배열을 이용한 평범한 배낭 문제와 마찬가지로 몇 번째 도시(보석)까지 고려했는 지는 dp에 표시 하지 않고 순서를 통해 표현한다. 도시를 여러 번 선택할 수 있으므로 반복문을 1에서 부터 bottom-up으로 탐색한다.

 

• dp[k]= 적어도 k명의 고객을 늘이기 위한 최소 비용

 

dp[a]에는 적어도 a명의 고객을 늘이기 위한 최소 비용이 저장된다. 즉, dp[a]의 비용이 dp[a+1]의 비용보다 클 수도 있으므로 일정 크기의 dp를 모두 구한 뒤 적어도 C이상의 고객을 얻는 비용 중 최소값을 반환하면 된다.(dp[C:])

이를 고려하기 위해 dp의 크기를 얻고자 하는 고객의 수보다 한 도시에서 얻을 수 있는 최대 고객의 수(100)만큼 크게 만들었다.

2-2. 코드

C, N = map(int, input().split()) # C - 적어도 얻고자 하는 이득 이 때 최소 비용 구하기
hotel=[[0,0]] #cost, benefit
for i in range(N):
    line= list(map(int, input().split()))
    hotel.append(line)

maxCost = float('INF')
dp= [maxCost for _ in range(C+100)]
dp[0]=0

for i in range(1, N+1):
    cost = hotel[i][0]
    benefit = hotel[i][1]
    
    for j in range(benefit, C+100):    
        dp[j] = min(dp[j], dp[j-benefit]+cost)
        
# print(dp)     
print(min(dp[C:]))