[백준] 7579 앱 (python 파이썬)

7579번: 앱

---

냅색 응용문제.

---

아이디어

냅색 알고리즘의 기본 원리를 이용해 해결할 수 있다. 

 

이차원 리스트 backpack[x][y]는 x번째 앱까지 y비용으로 얻을 수 있는 최대 메모리값이다.

 

1. 열의 크기는 제시된 모든 비용의 총합으로 한다.

 

2 - 1. 현재 앱의 비용 costList [i]가 j보다 크면 그대로 둔다.

backpack[i][j] = backpack[i - 1][j]

 

 2 - 2. j 가 더 크면 현재 앱의 유무를 비교해 값을 업데이트해준다. 

backpack[i][j] = max(backpack[i - 1][j], backpack[i - 1][j - costList[i]] + memoryList[i])

 

3. 현재 backpack[x][y]의 값이 M 이상이라면 정답을 최솟값 업데이트 해준다.

answer = min(answer, j)

---

전체 코드

N, M = map(int, input().split())

memoryList = [0] + [int(x) for x in input().split()]
costList = [0] + [int(x) for x in input().split()]

backpack = [[0] * (sum(costList) + 1) for _ in range(N + 1)]

answer = sum(costList)

for i in range(1, N + 1):
    for j in range(1, sum(costList) + 1):
        if j < costList[i]:
            backpack[i][j] = backpack[i - 1][j]

        else:
            backpack[i][j] = max(backpack[i - 1][j], backpack[i - 1][j - costList[i]] + memoryList[i])

        if backpack[i][j] >= M:
            answer = min(answer, j)

print(answer)