https://www.acmicpc.net/problem/12920
평범한 knapsack에 입력이 여러 N종류의 물건이 입력되며 같은 종류의 물건이 K개까지 있을 수 있는 문제다.
단순히 생각해 예를 들때 가치 10, 무게 1인 물건이 한개 두개가 아니라 1만개씩 들어오면
평범한 배낭 알고리즘 배울때 레퍼런스 코드에서는 가치10, 무게 1을 1만줄 입력하면된다.
이 1만줄 진짜로 무식하게 입력할거야? 묻는게 문제의 목적이다.
처음 이 문제를 접하고 몇일이고 머리가 안돌아서 다른분의 5년전 댓글에서 아이디어 힌트를 얻어서 풀었다.
"물건 3개를 넣는것을 고려하는것은 물건을 1개묶음과 2개묶음을 각각 넣는 경우를 고려하는것과 같다."
1개 넣는 경우 물건이 1개 필요하고
2개 넣는 경우 물건이 2개 필요하다.
그런데 3개를 넣을때 물건2개넣는 경우를 고려했으니 이 결과에 1개를 더 넣는 경우를 고려하면 3개를 넣는것을 고려하는것과 같다.
즉 2개를 묶음으로 넣는경우와 1개만 넣는 경우를 고려하면 물건 3개를 가방에 넣는 모든 경우를 고려한 것이다.
(이하 x개 고려 = (x) 로 적음)
(1) = 1 << (1) = 1
(2) = 2 << (2) = 1+1
(3) = 1+2 << (3) = 1+1+1
처음에 이 말만으로 고민하다 생각나는것은 개수를 1/2씩 계속 쪼개면 되지않을까 하는 생각이었다. (동생이 대신 생각해줬다)
예를 들어 50이 들어오면 25, 12(int 12.5), 6, 3, 1(int 1.5)이렇게 입력하는것이다.
이럴 경우 중간중간 빈부분이 생긴다. 이는 50 - (25+12+6+3+1)를 해서 나오는 오차인 3을 1,1,1로 입력해서 채울 수 있다.
총 입력은 25, 12, 6, 3, 1, 1, 1, 1 이렇게 7개가 나온다.
검산해보면 이 7개의 입력으로 물건을 1~50까지 가방에 물건을 넣는 경우를 고려할 수 있다.
(1) = 1
(2) = 1+1
(3) = 3
(4) = 1+3
...
(47) = 25+12+6+3+1
(48) = 25+12+6+3+1+1
(49) = 25+12+6+3+1+1+1
(50) = 25+12+6+3+1+1+1+1
이 방법도 좋다고 생각하고 실제로도 이정도로 입력을 줄이면 문제는 통과된다.
문제는 1이 많아졌다
아까 물건 3개를 넣을지 고려하는것은 1,2로 줄일수 있음을 알았는데 여기서 1이 더 많아지면 그걸 전부 일일이 교체할 것인가?
그래서 반대로 올라가봤다.
50이 주어지면 50에서 쪼개며 내려오는게 아니라
1에서 역으로 올라가는거다.
2진수를 생각하면 편하다. 0b001, 0b010, 0b100 == 1, 2, 4 이렇게 올라가는것이다.
n bit는 2^n-1까지 표현이 가능하다. 이는 2^n-1개를 넣을지 고려하는것은 n개입력으로 고려할 수 있다는 의미다.
7개를 넣을지 고려하는것은 1,2,4 3개의 입력으로 고려할 수 있다.
그러면 50과 같이 2^n-1로 딱 맞아떨어지지 않는수는 어떻게 할것인가?
이를 해결하기 위해 2^n-1까지만 표현하고 나머지는 묶음으로 처리해버렸다.
2^5-1, 5개의 입력으로 31개를 넣는 경우를 고려했다.
여기서 19개를 묶어서 넣는 경우를 고려하면된다.
이렇게하면 입력은 1,2,4,8,16, 19 으로 (5+1)6개가 들어온다.
검산을 해보면
2^5-1이 1~31개를 넣는 경우를 고려할 수 있고
여기에 19를 넣고 다시 고려하면 19+ 1~31(20~50)을 넣는 경우를 고려할 수 있다.
합하면 1~50을 넣는 모든 경우를 고려할 수 있다.
처음 방법보다 입력도 줄어서 시간적, 공간적 자원소모가 모두 개선된다.
같은물건을 N개 고려해야하면 N이 2^x-1로 나눠떨어지지 않는경우 log2(N) +1개로 나오게 된다.
즉, 처음 무식하게 N개 입력하는것을 log2(N)+1개 입력으로 줄여낸것이다!
이경우 시,공간 복잡도는 O(nm) -> O(logn * m)으로 탈바꿈!
입력만 위와같이 바꿔서 넣고 나머지는 기본적인 knapsack알고리즘의 틀을 그대로 가져다 쓴다.
입력코드
scanf("%d %d %d", &w, &v, &cnt);
int t = 1; int exp = 1;
while(exp <= cnt){
if(w * t > W) break;
wt[rear] = t*w;
val[rear] = t*v;
rear++;
t = t<<1;
exp += t;
}
exp -= t;
exp = cnt - exp;
if(exp > 0) {
wt[rear] = exp*w;
val[rear] = exp*v;
rear++;
}
소스 코드
한국어가 이렇게 어렵구나, 이를 더 쉽고 간단히 잘표현할 수 있을것같은데 내 한국어능력의 한계로 여기까지만 쓰는게 최선인것같다.
'PS > BOJ' 카테고리의 다른 글
| C - 13171 A (0) | 2023.12.14 |
|---|---|
| C - 17610 양팔저울 (3) | 2023.12.08 |
| C -15686 치킨 배달 (2) | 2023.12.05 |
| C - 12094 2048(hard) (0) | 2023.12.01 |
| C - 12100 2048(easy) (2) | 2023.12.01 |