이 글은 단순히 답을 적은 것이 아닌 답을 도출해내는 과정을 포함한 글입니다.
정답이 아닌 코드가 중간에 포함되어 있으니 정답 코드를 원하시는 분께선 맨 아래쪽으로 스크롤해주시기 바랍니다.
https://www.acmicpc.net/problem/12865
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
문제 설명
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
입력
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
출력
한 줄에 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 출력한다.
문제 풀이 과정
문제를 보고 아래의 방법들이 떠올랐다.
- DFS를 사용하여 모든 경우의 수 체크
- 1부터 K까지 각 무게마다 담을 수 있는 최댓값을 순서대로 구하기 (또는 반대로)
- 가장 많이 넣는 경우
- 무게를 전부 더한 뒤 초과되는 만큼 빼기
- 무게에 비해 가치가 큰것 우선으로 넣기
1번: DFS를 사용하여 모든 경우의 수 체크
물건을 넣었을 때, 넣지 않았을 때 2개의 가지로 나눠 모든 물건에 적용하는 것이다.
물건이 1개일 땐 경우의 수가 2개, 물건이 2개일 땐 경우의 수가 4개이다.
N의 값이 작을 땐 적용해도 크게 체감되진 않겠지만, N의 값이 커지면 커질수록 가짓수가 기하급수적으로 늘어난다.
따라서 1번 해결방법의 경우 현실적으로 불가능하다.
시간 복잡도가 O(2^n)이기 때문에 엣지 케이스인 100개의 물건이 주어졌다고 가정할 때, 가짓수가 2^100개나 되기 때문에 사실상 불가능하다.
2번: 1부터 K까지 각 무게마다 담을 수 있는 최댓값 순서대로 구하기
2번의 경우 문제가 조금 있다.
각 무게마다 담을 수 있는 최댓값을 구하고 최댓값끼리 더하여 다른 무게의 최댓값을 구했을 때, 같은 물건을 중복으로 담을 우려가 있다.
예시)
무게: 7
| 물건 번호 | 무게 | 가치 |
| 물건1 | 1 | 1 |
| 물건2 | 2 | 1 |
| 물건3 | 2 | 10 |
| 물건4 | 4 | 3 |
이런 케이스가 있다고 가정할 때, 무게 3과 4의 경우 최댓값은 11이다.
이때 무게 3과 4를 더해서 무게 7의 최댓값을 구하면, 물건 2가 중복으로 사용되어버린다.
또한 무게 7의 최댓값을 구하기 위해 1과 6을 더할지, 2와 5를 더할지, 3과 4를 더할지도 판별해야 한다.
개인적으로 이 방식이 가장 정답에 가까울것 같긴 한데, 일단은 다른 방법도 생각해봐야겠다.
3번: 가장 많이 넣는 경우
이건 확실히 안된다.
물건을 많이 넣는게넣는 게 목적이 아닌 가치가 높은걸 넣는 게 목적이기 때문에 무겁지만 가치가 큰 물건이 있을 때 이를 사용하지 못한다.
4번: 무게를 전부 더한 뒤 초과되는 만큼 빼기
이 방법은 근본적인 해결방법이라기보단 최적화에 어울리는 방법인 것 같다.
예를 들어 무게 1짜리 102개가 있고, 최대 무게는 100이라고 가정할 때, 100개를 더해 가장 가치가 큰 경우의 수를 찾는 방향보다 2개를 더해 가장 가치가 낮은 경우의 수를 찾는 방향으로 사용할 수 있을 것 같다.
5번: 무게에 비해 가치가 큰 것 우선으로 넣기
물건 하나하나의 가치를 각각의 무게로 나누고, 나눈 값이 큰 물건부터 채워 넣는 방법이다.
하지만 다음의 케이스에선 동작하지 않는다.
예시)
무게: 10
| 물건 번호 | 무게 | 가치 |
| 물건1 | 5 | 5 |
| 물건2 | 5 | 5 |
| 물건3 | 6 | 7 |
이런 케이스의 경우 물건3이 무게에 비해 가장 가치가 크다고 해서 넣으면, 물건을 하나밖에 넣지 못한다.
이 방법도 근본적인 해결방법이라기보단 정답에 가까운 경우의 수를 제공해주는 쪽으로 최적화를 시켜줄 수 있을 것 같다.
결국 문제의 핵심은 물건을 넣을 것인가, 뺄 것인가 인 것 같다.
2번의 방법에서 조금 변형하여, 다음과 같은 알고리즘을 구상해봤다.
우선 0부터 V까지의 배열을 만들고, 각각 0으로 초기화한다.
모든 물건에 대해 순차적으로 다음의 동작을 수행한다.
- 배열의 모든 인덱스 각각에 0이 아닌 값이 들어있는지 확인한다.
- 0이 아닌 값이 들어있다면, 배열[인덱스 + 물건의 무게]의 가치가 배열[인덱스] + 물건의 가치보다 작은지 확인한다.
- 만약 작다면, 해당 값으로 바꿔준다.
생각해보니 위의 동작을 수행할 때 오름차순으로 인덱스를 탐색하면 무게의 배수마다 값을 더해주게 되어버린다.
따라서 1번을 수행할 때 배열의 역순으로 탐색해야 한다.
예시)
무게: 8
| 물건 번호 | 무게 | 가치 |
| 물건1 | 2 | 2 |
| 물건2 | 1 | 1 |
| 물건3 | 1 | 2 |
| 물건4 | 4 | 5 |
| 물건5 | 6 | 7 |
진행 순서
1. 배열 초기화
2. 물건1
다른 물건이 들어와있지 않기 때문에, 자기 무게에 해당하는 인덱스에만 영향을 준다.
3. 물건2
다른 물건이 들어와있기 때문에 자신의 무게와 해당 물건 + 자신의 무게에 해당하는 인덱스에 영향을 준다.
4. 물건3
무게4: 0 < 3+2 (대체)
무게3: 3 < 2+2 (대체)
무게2: 2 < 1+2 (대체)
무게1: 1 < 2 (대체)
5. 물건4
무게8: 0 < 5+5 (대체)
무게7: 0 < 4+5 (대체)
무게6: 0 < 3+5 (대체)
무게5: 0 < 2+5 (대체)
무게4: 5 = 5
6. 물건5
무게6: 8 > 7
무게7: 9 = 2+7
무게8: 10 = 3+7
위의 알고리즘에 기반하여 코드를 작성했다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N, K;
int[] values = {0,};
int weight, value;
N = sc.nextInt();
K = sc.nextInt();
values = new int[K + 1]; //0 ~ K
for (int n=0; n<N; n++) {
weight = sc.nextInt();
value = sc.nextInt();
for(int i=K-weight; i>0; i--) { //의미없는 계산 방지
if(values[i] > 0) {
if (values[i + weight] < values[i] + value) {
values[i + weight] = values[i] + value;
}
}
}
if(values[weight] < value) {
values[weight] = value;
}
}
// for(int v: values) {
// System.out.print(v + " ");
// }
// System.out.println();
System.out.println(values[K]);
}
}
실패.
각 물건의 무게 범위가 1 <= W <= K가 아니라 1 <= W <= 100000이기 때문에 K보다 큰 W가 입력되었을 때 무시하도록 해줘야 한다.
weight과 value를 읽는 부분 뒤에 다음 코드를 추가했다.
if(weight > K) {
continue;
}
실패.
물건들의 무게를 더해도 K를 만들 수 없을 때를 생각해지 못했다.
예시)
1 2
1 1
위의 경우에 답은 1이지만, 내 알고리즘은 0을 출력한다.
물건들을 조합하여 나올 수 있는 무게만 최댓값이 저장되기 때문이다.
아래의 조건이 잘못되었다.
- 배열의 모든 인덱스 각각에 0이 아닌 값이 들어있는지 확인한다.
이 조건은 물건 하나하나가 모든 배낭 무게에 영향을 주지 않도록 넣은 조건문인데, 애초에 물건 하나하나가 배낭 무게에 영향을 줄 수밖에 없다는 점에서 전제 조건이 잘못되었다.
때문에 이 조건문이 없어야 더 큰 무게의 배낭도 처리 해줄 수 있다.
조건문을 다음과 같이 수정했다.
for(int i=K-weight; i>=0; i--) { //의미없는 계산 방지
if (values[i + weight] < values[i] + value) {
values[i + weight] = values[i] + value;
}
}
성공했다.
범위를 벗어난 입력과 필요없는 조건문을 빨리 알아차리지 못해 문제를 푸는데 시간이 걸렸던것 같다.
최종 코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N, K;
int[] values;
int weight, value;
N = sc.nextInt();
K = sc.nextInt();
values = new int[K + 1]; //0 ~ K
for (int n=0; n<N; n++) {
weight = sc.nextInt();
value = sc.nextInt();
if(weight > K) {
continue;
}
for(int i=K-weight; i>=0; i--) { //의미없는 계산 방지
if (values[i + weight] < values[i] + value) {
values[i + weight] = values[i] + value;
}
}
}
System.out.println(values[K]);
}
}
질문이나 개선사항은 언제든지 댓글로 남겨주세요.
이상으로 포스팅을 마치겠습니다.
'Algorithm' 카테고리의 다른 글
| [Algorithm] 3197번: 백조의 호수 (0) | 2021.06.22 |
|---|---|
| [Algorithm] 1655번: 가운데를 말해요 (0) | 2021.06.20 |
