정확히 배낭의 크기만큼 담아야하는 독특한 배낭 문제

13910번: 개업 (acmicpc.net)

 

n그릇의 요리를 해야하는데 가지고 있는 도구 크기들이 주어질때,

 

주어진 도구를 사용할때는 정확히 해당 크기만큼 요리해야한다면 n그릇을 만들기 위해 최소 몇번 요리해야하는지

 

예를 들어 1그릇, 3그릇용 도구가 주어지면 3그릇용 도구로 2그릇을 요리하지는 않고, 

 

1그릇용 도구만 사용하여 1그릇만 요리할 수도 있고

 

1그릇, 3그릇 도구를 동시에 써서 4그릇을 요리할 수도 있다

 

또한 4그릇을 만들어야할때, 5그릇을 만들지 않는다

 

 

배낭문제처럼 dp[i] = i그릇 요리를 만들기 위해 해야하는 최소 요리 수

 

0그릇 요리에는 당연히 0번이면 되니까 dp[0] = 0

 

i = 1,2,3,...,n에 대하여

 

j번째 도구를 사용할때, k = j+1,j+2,...,m-1번째 도구도 동시에 사용할 수도 있다고 한다면...(양손잡이니까)

 

한번에 요리는 v = A[j] 혹은 A[j] + A[k]만큼 할 수 있고

 

i그릇만큼 요리할려고 할때, 이것보다 많이 요리하지 않아야하므로 A[j]나 A[j]+A[k]가 i보다 크면 안된다

 

이러한 조건을 만족할때 dp[i]는 v그릇 덜 만들때 요리 횟수 dp[i-v]에 1 더한 dp[i] = min(dp[i], dp[i-v] + 1)

 

n,m = map(int,input().split())

A = list(map(int,input().split()))

INF = 10**12

dp = [INF]*(n+1)
dp[0] = 0

for i in range(1,n+1):
    
    for j in range(m):
        
        for k in range(j,m):
            
            if j == k:
                
                v = A[j]
            
            else:
                
                v = A[j] + A[k]

            if i >= v:

                dp[i] = min(dp[i], dp[i - v] + 1)

if dp[n] == INF:
    
    print(-1)

else:
    
    print(dp[n])

 

 

모든 경우를 조사했는데도 dp[n]이 INF로 갱신이 안된다면 불가능한 경우니까 -1을 출력

 

이게 뭔가 좀 어렵다면 처음에 만들 수 있는 모든 경우 A[j] + A[k]를 미리 만들어두고

 

목표 i = 1,2,3,..,n에 대하여 도구 j = S[0], S[1], S[2],...를 순회하는 방식으로

 

n,m = map(int,input().split())

A = list(map(int,input().split()))

#처음에 요리 가능한 그릇의 수를 모두 만들어두고
S = []

for i in range(m):
    
    S.append(A[i]) #한손으로 요리하는
    
    for j in range(i+1,m):
        
        S.append(A[i] + A[j]) #양손으로 요리하는

INF = 10**12

#dp[i] = i개 그릇 만드는데 해야하는 최소 요리 횟수
dp = [INF]*(n+1)
dp[0] = 0 #0그릇 만드는데 당연히 0번

#i = 1,2,3...,n에 대하여
for i in range(1,n+1):
    
    #가능한 만드는 요리 횟수...
    for j in range(len(S)):
        
        v = S[j]
        
        if i >= v: #i그릇을 만드는데 i그릇보다 더 많이 만들지는 않아야하므로

            dp[i] = min(dp[i], dp[i - v] + 1)

if dp[n] == INF:
    
    print(-1)

else:
    
    print(dp[n])