백준 12865: 평범한 배낭 [ JS ]

Song-Minhyung·2023년 2월 17일

Problem Solving

목록 보기

41/50

👉 문제

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

dp로 유명한 배낭문제다.
예전에 한번 푼적 있었는데 복습겸 다시 풀어보니 이제 확실하게 이해가 됐다.
문제는 최대 K만큼의 무게를 넣을 수 있는 배낭이 존재한다.
그리고 N개의 물건이 있는데 각각 무게 W와 가치 V를 가진다.
여기서 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하는 문제다.

1차원 배열을 쓰며 뒤부터 순환하며 푸는 방법과
2차원 배열을 쓰며 앞부터 순환하며 푸는 방법이 있다.

👉 접근

배낭에 물건을 넣을때 이 물건을 넣을지 넣지 말지 판단해야 한다.
이때 어떻게 판단할지 생각해보면 점화식이 세워진다.
예제에 있는 입력을 보면 어떻게 식을 세워야 할지 감이온다.

여기서 물건의 개수 N은 4, K는 7이므로 배낭에는 7만큼의 무게를 넣을 수 있다.
N: 4, K: 7

🧮 점화식

우선 물건을 넣거나 말거나 두가지 경우밖에 없기에 점화식이 간단해진다.

dp[ i ][ j ] = i 번째 물건을 넣을지 말지 결정하는 경우,
j무게 만큼 물건을 넣었을 때 가방에 넣을 수 있는 물건의 최대 가치이다.

정리하면
i = 현재 넣을지 말지 보고있는 물건
j = 현재 배낭의 무게고 현재 물건 i의 무게부터 끝까지 순환해본다.

점화식으로 표현하면 이렇다. 여기서 W는 물건의 무게, V는 가치다.

dp[ i ][ j ] = max (dp [ i - 1 ][ j - W ] + V, dp [ i - 1 ] ) 이다.

위의 개념으로 1차원 dp로 풀면 문제가 생길수도 있다.
왜 이렇게 되는지와 문제가 생길수 있는지는 예제의 물건 4개를 넣어보며 알아보도록 한다.

첫번째 물건을 넣는다.

dp[0] = 0이며 현재 dp는 아래와 같다.

1	2	3	4	5	6	7
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

그리고 첫번째 물건의 [W,V] = [6,13]이다.
그래서 6이상의 j는 전부 13이 차게된다.

1	2	3	4	5	6	7
0	0	0	0	0	13	13
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

두번째 물건을 넣는다.

두번째 물건의 [W,V] = [4, 8] 이다.

1	2	3	4	5	6	7
0	0	0	0	0	13	13
0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

물건을 넣으면 아래처럼 된다.

4	5	6	7
0	0	13	13
8	8	13	13
0	0	0	0
0	0	0	0

표를 보면 물건의 무게 W 이상만 비교를 하는걸 알수있다.
1. 1 ~ 3은 dp[i-1][j]값을 그대로 가져온다.
2. 4부터 dp[i-1][j-W] + V, dp[i-1][j]를 비교해 최댓값을 넣는다.

세번째 물건을 넣는다.

세번째 물건의 [W,V] = [3, 6] 이다.

4	5	6	7
0	0	13	13
8	8	13	13
0	0	0	0
0	0	0	0

위와 같은 방법으로 3 미만은 모두 그대로 가져오고 3부터 본다.

3	4	5	6	7
0	0	0	13	13
0	8	8	13	13
6	0	0	0	0
0	0	0	0	0

j가 7일때는 max( 8 + 6, 13 )을 해서 14가 나오게 된다.

3	4	5	6	7
0	0	0	13	13
0	8	8	13	13
6	8	8	13	14
0	0	0	0	0

네번째 물건을 넣는다.

[W, V] = [5, 12]다.

3	4	5	6	7
0	0	0	13	13
0	8	8	13	13
6	8	8	13	14
0	0	0	0	0

j가5 미만일때는 i-1의 값을 그대로 가져온다.

3	4	5	6	7
0	0	0	13	13
0	8	8	13	13
6	8	8	13	14
6	8	0	0	0

j가 5 ~ 7까지는 dp[i-1][j-W] + V 와 dp[i-1][j]를 비교해 더 큰값을 넣어준다.
이렇게

3	4	5	6	7
0	0	0	13	13
0	8	8	13	13
6	8	8	13	14
7	8	12	13	14

결과

그러고서 dp[N][K]를 출력해주면 된다.
위의 결과는 14다.

1차원 dp로 풀면 문제가 생기는 이유

만약 1차원 dp로 풀면 같은 물건이 여러번 들어가는 문제가 생긴다.
[W,V] = [2,3] 인경우를 생각해보면 i가 3일때까지는 값을 제대로 비교하며 넣는다.

1	2	3	4	5	6	7
0	3	3	0	0	0	0

그런데 i가 4일때 현재 물건을 넣었는데 또 넣게된다.
왜냐면 1차원 배열로 풀때 점화식은 이렇기 때문이다.

dp[ i ] = max ( dp[ i - W ] + V, dp[ i ] )

그래서 값을 채워나가면 i가 4~ 7일때 이렇게 된다.
자기 자신을 계속 더해나가는걸 볼수있다.

1	2	3	4	5	6	7
0	3	3	6	6	9	9

1차원 배열로 푸는방법?

그럼 1차원 배열로 풀수는 없을까? 당연히 방법이 있다.
배열을 앞이 아니라 맨 뒤부터 W까지만 순환하면 된다.

1차원 배열로 풀이를 하면 방금 변경된 값때문에 결과가 이상하게 나왔다.
그럼 방금 변경된 값을 참조하지 않게 뒤에서부터 순환을 하면 결과도 제대로 나온다.
그리고 메모리 사용량도 절반으로 줄어든다.

[W,V] = [2,3] 일때

dp[ 7 ] = max ( dp[ 7 - 2 ] + 3, dp[ 7 ] ) 이다.
dp[ 7 ] = max ( 3, 0 ) 이다.

1	2	3	4	5	6	7
0	0	0	0	0	0	3

dp[ 6 ] 일때도 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 0 | 0 | 0 | 0 | 3 | 3 |

dp 5~1까지도 보면 이렇다.
dp[ 5 ] = max ( dp[ 5 - 2 ] + 3, dp[ 5 ] )
dp[ 4 ] = max ( dp[ 4 - 2 ] + 3, dp[ 4 ] )
dp[ 3 ] = max ( dp[ 3 - 2 ] + 3, dp[ 3 ] )
dp[ 2 ] = max ( dp[ 2 - 2 ] + 3, dp[ 2 ] )
dp[ 1 ] = max ( dp[ 1 - 2 ] + 3, dp[ 1 ] )

식을 보면 내가 바꿨던 dp의 값은 참조하지 않는걸 볼수있다.

1차원 배열로 풀때 코드

const fs = require('fs');
const stdin = 
  fs.readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(Number);
})();

const [N, K] = input();
const dp = Array(K + 1).fill(0);

for (let i = 0; i < N; i++) {
  const [W, V] = input();
  for (let j = K; j >= W; j--) {
    if (dp[j - W] + V > dp[j]) {
      dp[j] = dp[j - W] + V;
    }
  }
}

console.log(dp[K]);

2차원 배열로 풀때 코드

const fs = require('fs');
const stdin = 
  fs.readFileSync(0, 'utf-8')
  .trim()
  .split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(Number);
})();


const [N, K] = input();
const dp = Array.from({ length: N + 1 }, () => Array(K + 1).fill(0));

for (let i = 1; i < N + 1; i++) {
  const [W, V] = input();
  for (let j = 1; j <= K; j++) {
    if (j - W >= 0) dp[i][j] = Math.max(dp[i - 1][j - W] + V, dp[i - 1][j]);
    else dp[i][j] = dp[i - 1][j];
  }
}

console.log(dp[N][K]);