알고리즘과 자료구조를 못하는 내가, 코테 문제들에서 항상 풀지 못한 유형의 문제다.
내가 항상 시도했던 방식은, dp 접근법이 아닌 백트래킹 접근법이였고, 코드는 아래와 같다.
#include <stdio.h>
int N;
int W;
int o[100][2];
int check[100];
int MAX = 0;
void pick(int w, int v) {
for(int i = 0; i < N; i++) {
if(!check[i] && w + o[i][0] <= W) {
check[i] = 1;
pick(w+o[i][0], v+o[i][1]);
check[i] = 0;
}
}
if(MAX <= v)
MAX = v;
}
int main() {
scanf("%d %d", &N, &W);
for(int i = 0; i < N; i++) {
scanf("%d %d", &o[i][0], &o[i][1] );
}
pick(0, 0);
printf("%d", MAX);
}당연히 시간초과가 떴다.
풀이는 두 가지로 정리했다.
- 2차원 dp 배열
dp[i][j] = i번째 물건까지 살펴봤을 때, j무게까지 담을 수 있는 최대 가치의 경우.
이렇게 되면, 총 물건 갯수가 N, 배낭 무게가 W라고 뒀을 때 dp[N][W] 값이, 우리가 구하는 정답이 된다.
▶︎ 말로 표현한 점화식
- i번째 물건이 배낭의 무게 한도보다 무거우면, i - 1번째 물건까지들로 구한 최적의 가치값을 그대로 사용한다.
- i번째 물건이 배낭의 무게 한도보다 무겁지 않으면, i번째 물건을 위해 i번째 물건의 무게만큼 비웠을때의 최적값에 i번째 물건의 가치를 더한 값 or i - 1번째 물건까지들로 구한 이전 단계의 최적의 가치값 중 큰 값을 사용한다.
말로 보면 언뜻 어려워보인다. 우선 문제의 예제 내용을 통해 풀이해보자.
총 물건 갯수 : 4
총 배낭 무게 : 7
| 무게 | 가치 | |
| 첫번째 물건 | 6 | 13 |
| 두번째 물건 | 4 | 8 |
| 세번째 물건 | 3 | 6 |
| 네번째 물건 | 5 | 12 |
dp 배열에 대한 표를 만드는데, dp[0][k] 는 물건이 0번째 = 없는 경우 이므로 모두 0으로 채우고, dp[k][0]인 경우 배낭의 무게 한도가 0인 경우이므로 모두 0으로 채운다.
물건 = i , 배낭 무게 = j
| i / w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | |||||||
| 2 | 0 | |||||||
| 3 | 0 | |||||||
| 4 | 0 |
i 번째 물건의 무게를 w[i], 가치를 v[i]라고 했을 때, 첫 번째 물건을 담는 경우부터 알아가보자.
∙ 첫번째 물건( i = 1) / w[1] = 6, v[1] = 13
배낭의 무게가 1일 때 = dp[1][1], 첫 번째 물건을 담지 못한다.
배낭의 무게가 2일 때 = dp[1][2], 첫 번째 물건을 담지 못한다.
...
배낭의 무게가 6일 때 = dp[1][6], 첫 번째 물건을 담을 수 있다.
배낭의 무게가 7일 때 = dp[1][7], 첫 번째 물건을 담을 수 있다.
이 결과가 아까 말로 표현한 점화식의 경우에 대한 상세 과정인 셈이다.
| i / w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2 | 0 | |||||||
| 3 | 0 | |||||||
| 4 | 0 |
∙ 두번째 물건( i = 2) / w[2] = 4, v[2] = 8
배낭의 무게가 1일 때 = dp[2][1], 두 번째 물건을 담지 못한다.
배낭의 무게가 2일 때 = dp[2][2], 두 번째 물건을 담지 못한다.
...
배낭의 무게가 4일 때 = dp[2][4], 두 번째 물건을 담을 수 있다.
배낭의 무게가 5일 때 = dp[2][5], 두 번째 물건을 담을 수 있다.
배낭의 무게가 6일 때 = dp[2][6], 두 번째 물건을 담을 수 있다.
배낭의 무게가 7일 때 = dp[2][7], 두 번째 물건을 담을 수 있다.
이제, 아까 말로 설명한 점화식을 정확하게 정리할 때가 왔다.
1. i 번째 물건을 담을 수 없을 때, i - 1번째 물건까지들로 구한 최적의 가치값을 그대로 사용한다.
= dp[i][j] = dp[i - 1][j]
2. i 번째 물건을 담을 수 있을 때, i번째 물건을 위해 i번째 물건의 무게만큼 비웠을때의 최적값에 i번째 물건의 가치를 더한 값 or i - 1번째 물건까지들로 구한 이전 단계의 최적의 가치값 중 큰 값을 사용한다
= dp[i][j] = MAX(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
두 번째 물건을 담는 경우로 돌아와보자.
'직관적인 결과' ▶︎ '점화식의 실제 이용' 형태로 그려보겠다.
배낭의 무게가 1일 때 = dp[2][1], 두 번째 물건을 담지 못한다
▶︎ dp[1][1] = dp[1][1] = 0
배낭의 무게가 2일 때 = dp[2][2], 두 번째 물건을 담지 못한다
▶︎ dp[1][2] = dp[1][2] = 0
...
배낭의 무게가 4일 때 = dp[2][4], 두 번째 물건을 담을 수 있다.
▶︎ dp[2][4] = MAX(dp[1][4 - w[2]] + v[2], dp[1][4]) = MAX(8, 0) = 8
배낭의 무게가 5일 때 = dp[2][5], 두 번째 물건을 담을 수 있다.
▶︎ dp[2][5] = MAX(dp[1][5 - w[2]] + v[2], dp[1][5]) = MAX(8, 0) = 8
배낭의 무게가 6일 때 = dp[2][6], 두 번째 물건을 담을 수 있다.
▶︎ dp[2][6] = MAX(dp[1][6 - w[2]] + v[2], dp[1][6]) = MAX(8, 13) = 13
| i / w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2 | 0 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3 | 0 | |||||||
| 4 | 0 |
이제 세 번째 물건의 경우에 대해 알아보자.
∙ 세 번째 물건 (i = 3) / w[3] = 3, v[3] = 6
배낭의 무게가 1일 때, 세 번째 물건을 담지 못한다.
▶︎ dp[3][1] = dp[2][1] = 0
...
배낭의 무게가 3일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[3][3] = MAX(dp[2][3 - w[3]] + v[3], dp[2][3]) = MAX(6, 0) = 6
배낭의 무게가 4일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[3][4] = MAX(dp[2][4 - w[3]] + v[3], dp[2][4]) = MAX(6, 8) = 8
...
배낭의 무게가 7일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[3][7] = MAX(dp[2][7 - w[3]] + v[3], dp[2][7]) = MAX(dp[2][4] + 6, 13) = MAX(14, 13) = 14
| i / w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2 | 0 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3 | 0 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| 4 | 0 |
마지막 네 번째 물건의 경우에 대해 알아보자. 여기선 눈에 띄게 달라지는점이 생긴다.
∙ 네 번째 물건 (i = 4) / w[4] = 5, v[4] = 12
배낭의 무게가 1일 때, 네 번째 물건을 담지 못한다.
▶︎ dp[4][1] = dp[3][1] = 0
...
배낭의 무게가 3일 때, 네 번째 물건을 담지 못한다.
▶︎ dp[4][3] = dp[3][3] = 6
여태까지 물건을 담지 못할 경우에 dp[i - 1][j] 를 참조한다는 것은 알았는데, 그게 항상 0의 값이기만 했다.
이 경우에, dp[i - 1][j]를 확실히 이해하는 도움을 주게 된다.
즉, 네 번째 물건을 담지 못하므로, 같은 가방 무게에서 이전 물건까지(세번째 까지 올라온 경우까지) 담아왔던 경우의 최댓값을 그대로 이용하는 것이다. 다시말해 네 번째 물건을 담지 못하는 대신에 세 번째 물건을 담은 것.
...
배낭의 무게가 5일 때, 네 번째 물건을 담을 수 있다.
▶︎ dp[4][5] = MAX(dp[3][5 - w[4]] + v[4], dp[3][5]) = MAX(dp[3][0] + 12, 8) = MAX(12, 8) = 12
배낭의 무게가 6일 때, 네 번째 물건을 담을 수 있다.
▶︎ dp[4][6] = MAX(dp[3][6 - w[4]] + v[4], dp[3][6]) = MAX(dp[3][1] + 12, 13) = MAX(12, 13) = 13
배낭의 무게가 7일 때, 네 번째 물건을 담을 수 있다.
▶︎ dp[4][7] = MAX(dp[3][7 - w[4]] + v[4], dp[3][7]) = MAX(dp[3][2] + 12, 14) = MAX(12, 14) = 14
| i / w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| 2 | 0 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| 3 | 0 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| 4 | 0 | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
그럼 dp[4][7] = 14. 그리고 이게 우리가 구해야 하는 정답이 된다.
이를 코드로 구현하면 아래와 같다.
#include <stdio.h>
#define MAX(a,b) (a>=b)?a:b
int N;
int W;
int weight[101];
int value[101];
int dp[101][100001];
int main() {
scanf("%d %d", &N, &W); // 총 물건 갯수 , 가방 무게
for(int i = 1; i <= N; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
// dp[i][j] = i번째 물건까지 살펴봤을 때, j무게까지 담을 수 있는 최대 가치 경우.
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= W; j++) {
if(j >= weight[i]) { // i 번쨰 물건을 넣을 수 있다면
// 이전에 담았던 최댓값과, 담게 된 경우의 최댓값을 비교하여 둘 중의 큰 값을 최댓값으로 지정.
dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - weight[i]]+value[i]); // 이게맞음. 설명코드가 잘못되심.
} else { // 담을 수 없으면, 이전에 담았던 물건의 최대값(dp[i - 1][j]) 그대로 사용.
dp[i][j] = dp[i - 1][j];
}
}
}
printf("%d", dp[N][W]);
}
dp[N][W] 라고 해서, N번째 물건이 꼭 들어갔다고 의미되는게 아니다.
선택 안하는 경우가 있었듯이, 포문을 통해 'i 번째 물건까지 살펴봤을 때, 최댓값'을 구해나가면서 그 최댓값을 이어지게 만든다.
이렇게해서 dp[N][W] 에는,'N번째 물건까지 살펴봤을 때, 가방 한도가 W인 상황에서 최대로 들어갈 수 있는 가치 값'이 도출되게 된다.
{ 참고 }
dp 배열은, 문제에서 주어진 dp[최대물건갯수 + 1][최대 물건 무게 + 1] 로 선언한다.
-> dp[0][k] 는 0번째 물건에 대한 값이므로 불필요하고, dp[k][0]은 무게가 0인 경우니까 불필요하다.
- 1차원 dp 배열
위에서는 2차원 dp배열로 문제를 풀었는데, 1차원 dp배열로도 문제 풀이가 가능하며, 더 빠르기까지 하다.
1차원 dp 풀이에서도 dp배열의 의미는 마찬가지로 동일하다.
dp[j] = 가방 한도가 j인 상황에서의 최대 가치값
배열을 일차원으로 사용하기 때문에, 배낭의 무게보다 물건이 더 무거워서 담지 못하는 경우에 대한 처리가 필요없고(중첩되면서 값이 이미 들어있음), 이전 물건까지의 최댓값을 dp[j - 1]에서 가져오는게 아니라 자기 자신에서 가져오게 된다(현재 물건을 담지 않는 최대경우가 이미 dp[j]에 들어있음).
대신 이러한 특징으로, 주의해야 할 점이 생긴다. 2차원 풀이에서는 가방의 한도 무게를 1 ~ W 까지 돌았지만, 1차원 풀이에서는 가방의 한도 무게를 W ~ 1까지 거꾸로 진행한다.
왜 그런지는 천천히 풀이를 따라가보면 받아들이게 된다.
▶︎ 말로 표현한 점화식
- 물건이 배낭의 무게 한도보다 무거우면, 아무런 작업을 해주지 않는다.
- 물건이 배낭의 무게 한도보다 무겁지 않으면, i번째 물건을 위해 i번째 물건의 무게만큼 비웠을때의 최적값에 i번째 물건의 가치를 더한 값 or 현재 dp값 중 큰 값을 사용한다.
똑같은 예제로 진행해보자.
총 물건 갯수 : 4
총 배낭 무게 : 7
| 무게 | 가치 | |
| 첫번째 물건 | 6 | 13 |
| 두번째 물건 | 4 | 8 |
| 세번째 물건 | 3 | 6 |
| 네번째 물건 | 5 | 12 |
배낭 무게 = j
dp 배열의 기본값은 모두 0.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
이전과 달리 이차원 배열이 아닌 일차원 배열로 진행된다. 또한 배낭의 무게를 1 ~ W 까지가 아닌 W ~ 1까지 거꾸로 돈다.
∙ 첫 번째 물건 / w[1] = 6, v[1] = 13
배낭의 무게가 7일 때, 첫 번째 물건을 담을 수 있다.
▶︎ dp[7] = MAX(dp[7 - w[1]] + v[1], dp[7]) = MAX(13, 0) = 13
배낭의 무게가 6일 때, 첫 번째 물건을 담을 수 있다.
▶︎ dp[6] = MAX(dp[6 - w[1]] + v[1], dp[6]) = MAX(13, 0) = 13
...
배낭의 무게가 5일 때, 첫 번째 물건을 담을 수 없다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
이전과 달리 담을 수 없는 경우에 대해서는, 별도로 처리하지 않아도 된다.
∙ 두 번째 물건 / w[2] = 4, v[2] = 8
배낭의 무게가 7일 때, 두 번째 물건을 담을 수 있다.
▶︎ dp[7] = MAX(dp[7 - w[2]] + v[2], dp[7]) = MAX(8, 13) = 13
배낭의 무게가 6일 때, 두 번째 물건을 담을 수 있다.
▶︎ dp[6] = MAX(dp[6 - w[2]] + v[2], dp[6]) = MAX(8, 13) = 13
배낭의 무게가 5일 때, 두 번째 물건을 담을 수 있다.
▶︎ dp[5] = MAX(dp[5 - w[2]] + v[2], dp[5]) = MAX(8, 0) = 8
배낭의 무게가 4일 때, 두 번째 물건을 담을 수 있다.
▶︎ dp[4] = MAX(dp[4 - w[2]] + v[2], dp[4]) = MAX(8, 0) = 8
배낭의 무게가 3일 때, 두 번째 물건을 담을 수 없다.
...
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
∙ 세 번째 물건 / w[3] = 3, v[3] = 6
배낭의 무게가 7일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[7] = MAX(dp[7 - w[3]] + v[3], dp[7]) = MAX(dp[4] + 6, 13) = MAX(14, 13) = 14
배낭의 무게가 6일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[6] = MAX(dp[6 - w[3]] + v[3], dp[6]) = MAX(dp[3] + 6, 13) = MAX(6, 13) = 13
...
배낭의 무게가 3일 때, 세 번째 물건을 담을 수 있다.
▶︎ dp[3] = MAX(dp[3 - w[3]] + v[3], dp[3]) = MAX(dp[0] + 6, 0) = MAX(6, 0) = 6
배낭의 무게가 2일 때, 세 번째 물건을 담을 수 없다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
∙네 번째 물건 / w[4] = 5 , v[4] = 12
...
배낭의 무게가 5일 때, 네 번째 물건을 담을 수 있다.
▶︎ dp[5] = MAX(dp[5 - w[4]] + v[4], dp[5]) = MAX(dp[1] + 12, 8) = MAX(12, 8) = 12
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 0 | 0 | 0 | 0 | 8 | 12 | 13 | 14 |
결과는, dp를 2차원배열로 했을 때 마지막 물건 행과 동일하다.
이렇게 1차원배열로 중첩적으로 돌기 때문에, 물건을 담지 못하는 경우에 대한 처리를 해 주지 않아도 되며
현재 물건에 대한 for문을 돌기 전에 당연히 이전 물건에 대한 for문을 돌면서 배열에 값을 처리해주었기 때문에 dp[k] 에는 같은 k무게에서 이전 물건까지의 최댓값이 들어있으므로 dp[j - 1] 같은 참조를 하지 않아도 된다.
여기서, 왜 배낭 무게를 오름차순으로 돌면 안되냐고 궁금해하는 분들이 계실 것 같아서 직접 보여드리겠다.
배열을 1차원을 사용해도, 물건 / 가방 한도별로 포문을 도는 것은 동일했다.
대신 일차원 배열은 위에서 말한 특징이 있기 때문에, 오름차순으로 돌게 되면 아래와 같은 문제점이 생긴다.
| 총 물건 | 2 |
| 배낭 한도 | 6 |
| 무게 | 가치 | |
| 첫 번째 물건 | 1 | 2 |
| 두 번째 물건 | 1 | 3 |
첫 번째 물건만 뽑아봐도 답이 나온다.
배낭의 무게가 1일 때, 첫 번째 물건을 담을 수 있다.
▶︎ dp[1] = MAX(dp[1], dp[1 - w[1]] +v[1]) = MAX(0, dp[0] + 1) = 1
배낭의 무게가 2일 때, 첫 번째 물건을 담을 수 있다.
▶︎ dp[2] = MAX(dp[2], dp[2 w[1]] + v[1]) = MAX(0, dp[1] + 1) = 2
dp[1]에서 첫 번째 물건을 담아서 dp[1] 값을 업데이트했다.
dp[2]에서, 첫 번째 물건으로 업데이트된 dp[1] 값을 다시 사용한다.
이렇게 되면, 물건을 중복해서 담는 경우가 생긴다.
그래서 뒤에서부터 포문을 돌아서, 물건별 포문 안에서 물건을 여러번 담는 에러를 방지하는 것이다.
(현재 단계에서 업데이트한 dp값의 재사용 방지)
코드는 아래와 같다.
// 일차원이기 때문에, 안들어가는 경우에 대한 처리가 필요없고, dp[j - 1]에서 가져오는게 아니라 자기 자신에서 가져오게 된다.
// 대신 이러한 특징을 가진 일차원배열로 하기 때문에 고려해야하는점이 바로 앞에서부터 뒤가 아닌 뒤에서부터 앞으로 돌아야 한다는 것이다.
// 이번 물건에 대한 포문에서
// dp[2] = MAX(dp[1], dp[2 - 1] + 1) = 3 업데이트했다고 보자.
// j가 올라가다가 3이 되었는데, dp[4] = MAX(dp[4], dp[3 - 1] + 2) 이런식이 되면, 방금 업데이트한 dp[2] 를 참조하게 된다.
// 이번 물건에 대해 두번 뽑는 경우가 생긴다는 것.
#include <stdio.h>
#define MAX(a,b) (a>=b)?a:b
int N;
int W;
int weight[101];
int value[101];
int dp[100001];
int main() {
scanf("%d %d", &N, &W);
for(int i = 1; i <= N; i++) {
scanf("%d %d", &weight[i], &value[i]);
}
for(int i = 1; i <= N; i++) {
for(int j = W; j >= 1; j--) {
if(j >= weight[i]) {
dp[j] = MAX(dp[j], dp[j - weight[i]]+value[i]);
}
}
}
printf("%d", dp[W]);
}
참고 블로그 추천
( 냅색 문제에 대한 전체적인 이해 )
( 해당 문제에 대한 표 이해 )
3. chanhuiseok.github.io/posts/improve-6/
( 일차원 / 이차원 경우에 대한 이해.. 하지만 2차원 코드는 틀린 부분이 있고, 1차원 표도 틀린 부분이 있다 )
4. www.acmicpc.net/board/view/43002
( 1차원 배열의 경우 내림차순을 사용해야 하는 참고 )
5. www.acmicpc.net/source/24810419
( 정리된 2차원 배열 코드 참고 )
2021.02.26 복습
다시풀어보았다.
2차원 배열 풀이
#include <stdio.h>
#define MAX(a,b) ((a>=b)?a:b)
int N;
int K;
int W[101];
int V[101];
int dp[101][100001];
int main() {
scanf("%d %d", &N, &K);
for(int i = 1; i <= N; i++) {
scanf("%d %d", &W[i], &V[i]);
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
if(W[i] <= j) { // 담을 수 있다면
dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
}
else { // 담을 수 없다면
dp[i][j] = dp[i - 1][j];
}
}
}
printf("%d", dp[N][K]);
}
/*
냅색 문제.
6 13
4 8
3 6
5 12
dp[i][j] = i번째 물건까지 살펴봤을 때, j무게까지 담을 수 있는 가치의 최댓값.
A. 넣는 경우 ( 가방에 여유가 있다 -> w[i] <= j )
dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
동일한 무게로 이전 물건까지 살펴봤던 최댓값 or 이전 물건까지 살펴본 최댓값(dp[i-1][?])들 중 담을 무게를 비운 값(dp[i-1][j - w[i]])
B. 넣지 않는 경우 ( 가방에 여유가 없다 -> w[i] > j )
dp[i][j] = dp[i - 1][j]
동일한 무게로 이전 물건까지 살펴봤던 최댓값을 그대로 사용.
*/
1차원 배열 풀이 ( 2차원에서 조금만 손봐주면 된다. )
#include <stdio.h>
#define MAX(a,b) ((a>=b)?a:b)
int N;
int K;
int W[101];
int V[101];
int dp[100001];
int main() {
scanf("%d %d", &N, &K);
for(int i = 1; i <= N; i++) {
scanf("%d %d", &W[i], &V[i]);
}
for(int i = 1; i <= N; i++) {
for(int j = K; j >= 1; j--) {
if(W[i] <= j) { // 담을 수 있다면
dp[j] = MAX(dp[j], dp[j - W[i]] + V[i]);
}
}
}
printf("%d", dp[K]);
}1차원 배열 풀이는
- 무게를 뒤에서부터 앞으로 계산한다는 점
(1차원으로 작업하기 때문에, 현재 물건에 대한 고려값이 또다시 현재에 재사용되는걸 방지하기 위해)
- 물건을 담지 못하는 경우에 대한 처리가 따로 필요하지 않다는 점
(1차원으로 중첩계산이기에 해줄 필요 없음)
'[백준]' 카테고리의 다른 글
| [BaekJoon/백준] 1931번 [동적계획법 VS 그리디 알고리즘 정리 2차] | 복습 1회 완료 (0) | 2021.02.04 |
|---|---|
| [BaekJoon/백준] 11047번 [ 그리디 알고리즘 ] (0) | 2021.02.03 |
| [BaekJoon/백준] 1912번 | 복습 1회 완료 (0) | 2021.02.01 |
| [BaekJoon/백준] 11653번 (0) | 2021.01.30 |
| [BaekJoon/백준] 10757번 (1) | 2021.01.29 |