[백준] 1315번 배낭 - Python

백준 실버3 1315번 배낭 - Python

https://www.acmicpc.net/problem/1535

1535번: 안녕

---

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 31256KB | 시간 40ms | 코드 길이 371B

N = int(input())
L = [int(x) for x in input().split()]
J = [int(x) for x in input().split()]
L, J = [0] + L, [0] + J
dp = [[0 for _ in range(101)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, 101):
        if L[i] <= j:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-L[i]] + J[i])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][99])

배낭(Knapsack) 알고리즘을 이용한 풀이입니다.

 

이 문제는 두가지로 접근이 가능한데요,

 

우선 하나는 브루트포스입니다. n명의 사람이 있을 때, 2^n 가지의 모든 경우를 따져보아야합니다.

이러한 O(2^n) 의 알고리즘으로 접근하기에는 시간복잡도에 큰 영향을 미치기에 따져보지 않겠습니다.

 

그래서 나머지 하나의 접근인 다이나믹 프로그래밍(배낭 알고리즘)으로 문제를 풀어보겠습니다.

 

• 아래와 같은 표를 생각합니다.
• 열은 L과 J를 말합니다. ( 체력 , 기쁨 )
• 표에 들어갈 내용은 bp리스트에 들어가는 내용입니다.
• 참고로, bp리스트는 이중리스트이며, bp[ 사람번호 i ] [ 최대 체력 j ]
• 스케일을 줄여서 세준이의 체력이 6(6일때는 die해버리니 5를 최대로 줍니다.)이라고하고,
  4명의 사람을 준비해봅시다.

• i = 1 일 경우를 생각해봅니다.
• 만약 j = 1 일 경우에는 체력을 2 이상이어야 쓸 수 있으므로 0입니다.

• j = 2 일 경우에는 (2,3) 인 사람이 3의 기쁨을 줄 수 있습니다.
• 2 이상인 경우에도 마찬가지이므로 표를 이렇게 채우놓을 수 있겠죠? (코드 구조상 j먼저 돌아야 함)

• 다음 순서인 i = 2 경우를 생각해봅시다.
• j = 1 인 경우에는 넣지 못하므로 0이 들어가고, 2인 경우에는 bp[1][2] 인 3이 들어갑니다.
  i = 2, j = 2 인 경우까지는 최대 3의 기쁨을 얻을 수 있기 때문입니다. bp[i-1][j] 가 들어간 거죠.
  else문의 경우입니다.

• 그러나 최대 체력이 3일 경우에는 두번째 사람도 들어갈 수 있습니다.
• 이럴 때 bp[i-1][j] 와 bp[i-1][j-L[j]] + J[j] 중 큰 수를 bp[i][j] 에 넣어야합니다.
  bp[i-1][j] 는 같은 체력(j)에 이전 사람(i-1)의 기쁨 이고
  bp[i-1][j-L[j]] + J[j] 는 현재 사람이 응원을 하게 될 때를 위해 체력을 미리 비워두고 기쁨을 더해줍니다.

• 그리고 bp[2][5] 에는 첫번째와 두번째 모두 들어갈 수 있겠죠? 그럼 3+4 입니다.
• 3은 어디서 온거라고요? bp[2-1][5-3] = bp[1][2] = 3 에서 온 것입니다.
  4는요? J[2] = 4 에서 온것이죠? 잘하셨습니다!

• 이런식으로 나머지도 채워볼까요?

이렇게 마지막에 들어간 수인 bp[4][5] = 7 가 최대로 느낄 수 있는 기쁨이 됩니다.

---

Search 🔍

• 코드 참고 : https://sangminlog.tistory.com/entry/boj-1535#recentEntries
• 배낭 알고리즘 : https://jeonyeohun.tistory.com/86

---

후기

이제 할 일을 다 했으니 게임을 해야겠군용 ㅋ

근데 문제 또 풀어야함 ㅎ.