index와 value를 바꾸는 다이나믹 프로그래밍 트릭

E - Maximum Glutton (atcoder.jp)

E - Maximum Glutton

 

단맛이 a 짠맛이 b로 주어지는 n개의 음식을 먹는데

 

단맛이 x를 초과하거나 짠맛이 y를 초과하는 순간 음식을 그만 먹는다면

 

음식을 최대한 많이 먹고자할때, 최대로 먹을 수 있는 음식의 수는?

 

전형적인 배낭 문제라서 dp[i][j][k] = i번째 음식까지 먹었을때 단맛의 합이 j, 짠맛의 합이 k인 경우 먹은 최대 음식의 수로 

 

하면 될것 같다고 생각을 했는데

 

n이 80이고 a가 10000, b가 10000까지라서  8*10^9라 시간초과에 메모리도 초과..

 

이럴 때 필요한게 " swapping the key and value of DP"라고 함

 

전형적인 접근법이라는데 나는 처음들어봄..

 

dp[i][j][k] = i번째 음식까지 먹었을 때 단맛의 합이 k가 되도록 먹은 음식의 수가 j개일때 짠맛의 합의 최솟값

 

이렇게 하면 i = 1,2,3,..,n이고 j = 1,2,3,...,n이고 k = 1,2,3,..,x(x를 넘으면 안되므로)까지니까

 

$O(N^{2}X)$에 dp테이블을 채울 수 있다

 

그리고 n번째 음식까지 먹었을 때, 모든 j = n,n-1,n-2,...,0에 대하여 k = 1,2,3,..,x에 대해 dp[n][j][k] <= y인

 

j를 찾는다면 그러한 j가 단맛의 합이 x를 넘지 않고 짠맛의 합도 y를 넘지 않는 먹은 음식의 개수의 최댓값이 된다

 

여기에 1개를 더 먹으면 단맛의 합이 x를 넘거나 짠맛의 합이 y를 넘게 되므로 그 순간 음식을 더 이상 먹지 않으니

 

j+1이 정답이다

 

#단맛이 a, 짠맛이 b인 n개의 음식을 먹을때
#단맛의 합이 x를 넘지 않거나 y를 넘지 않도록 최대로 먹을 수 있는 개수

n,x,y = map(int,input().split())

f = []

for _ in range(n):
    
    a,b = map(int,input().split())

    f.append((a,b))

#전형적인 배낭 문제
#dp[i][j][k] = i번째 음식까지 단맛의 합이 j, 짠맛의 합이 k가 되도록 먹은 최대 음식의 개수(O(NXY), 8*10^9로 시간초과)

#dp[i][j][k] = i번째 음식까지 단맛의 합이 k가 되도록 j개를 선택할때 짠맛의 최솟값(O(N^2X) 64*10^6으로 가능)

INF = 10**6

dp = [[[INF]*(x+1) for _ in range(n+1)] for _ in range(n)]

a,b = f[0]

dp[0][0][0] = 0

if a <= x:

    dp[0][1][a] = b

for i in range(1,n):
    
    a,b = f[i]

    for j in range(n+1):
        
        for k in range(x,-1,-1):
            
            dp[i][j][k] = min(dp[i-1][j][k], dp[i][j][k]) #i번째 음식을 먹지 않아도 먹은게 j개이고 단맛 합이 k가 되는 경우가 있다

            if j >= 1 and k-a >= 0:

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


#n번째까지 음식 먹었을 때 dp[n-1]
#먹은 음식의 수가 i개이고 단맛의 합이 j인 경우 dp[n-1][i][j]
#이 짠맛의 합의 최솟값이 y이하가 되는 i의 최댓값을 찾으면

#i+1이면 단맛의 합이 x를 넘거나 짠맛의 합이 y를 넘게 된다
answer = 0

for i in range(n-1,0,-1):
    
    for j in range(x+1):
        
        if dp[n-1][i][j] <= y: 
            
            answer = i
            break
    
    if answer != 0:
        
        break

print(answer+1)

 

 

배낭문제다 보니까.. dp[i][j][k]에서 i부분을 지우고 2차원 배열로 할 수도 있을 것 같다

 

https://deepdata.tistory.com/1286

0-1 knapsack 배낭 문제 해법 반드시 알아야하는 디테일(물건을 중복해서 담는 경우)

 

 

dp[i][j] = 단맛의 합이 j가 되도록 i개의 음식을 먹을때, 짠맛의 합의 최솟값

 

이렇게 하면 1차원 배열 knapsack한것 처럼 i,j 모두 역순으로 돌아줘야함

 

이렇게 하면 메모리도 아끼는것은 물론이고 시간도 빨라짐

 

 

#배낭 문제니까 dp[i][j][k]에서 i부분을 지워서 2차원 배열로 만들 수 있을 것 같다
n,x,y = map(int,input().split())

f = []

for _ in range(n):
    
    a,b = map(int,input().split())

    f.append((a,b))

#dp[j][k] = 단맛의 합이 k가 되도록 j개를 선택할때 짠맛의 최솟값

INF = 10**6

dp = [[INF]*(x+1) for _ in range(n+1)]

a,b = f[0]

dp[0][0] = 0

if a <= x:

    dp[1][a] = b

#O(N^2X)긴 한데 3차원 배열로 구할때보다 시간도 훨씬 빠르고 메모리도 덜 든다
for i in range(1,n):
    
    a,b = f[i]
    
    for j in range(n,-1,-1):
        
        for k in range(x,-1,-1):
            
            if j >= 1 and k-a >= 0:

                dp[j][k] = min(dp[j-1][k-a] + b, dp[j][k])

answer = 0

for i in range(n-1,0,-1):
    
    for j in range(x+1):
        
        if dp[i][j] <= y:
            
            answer = i
            break
    
    if answer != 0:
        
        break

print(answer+1)