#12920: 평범한 배낭 2

 

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

12920번: 평범한 배낭 2

---

Introduction

PS를 처음 시작했을 때 평범한 배낭 1을 풀고 바로 도전했다가, 3개월이 지난 지금에야 풀었다.

LCA를 공부하면서 2의 거듭제곱을 잘 활용하는 것이 시간을 줄일 수 있는 접근법이란 걸 배웠는데, 여기서도 마찬가지이다. 사실 온전히 내 힘으로 풀진 못했고, 구글에 돌아다니는 힌트를 봤다.

---

Body

앞서 설명했듯 이 문제는 '모든 자연수는 2의 거듭제곱의 합으로 표현 가능하다'는 명제를 잘 생각해보면 평범한 배낭 1과 다를 바가 없는 문제이다. '평범한 배낭 1'을 풀었다면, 시간을 줄이기만 하면 될 테니까 말이다.

 

2진법을 생각해보면 k가 10일 때, 1~10까지 돌면서 반영해야 할 것을, 1, 2, 4, 3 < 이렇게 4번으로 줄일 수 있다.

k가 17이면, 1, 2, 4, 8, 2.

 

원래 17*x번 연산해야 할 것을 5*x번으로 줄일 수 있다.

3 = 1+2

5 = 1+4

6 = 2+4

7 = 1+2+4

---

17까지 해보면 이해가 갈 것이다.

---

code

tempk = 1;
while (K > 0) {
	tempk = min(tempk, K);
	for (int j = M; j >= tempk * W; j--) {
		if (result[j - tempk * W] != 0 || j == tempk * W)
			result[j] = max(result[j - tempk * W] + tempk * V, result[j]);
	}
	K -= tempk; //17, 16, 14, 10, 2, 0
	tempk *= 2; //1, 2, 4, 8, 2, 4(x)
}

따라서 k가 10일 때, 1~10까지 돌아주면서 갱신하던 것을, 2의 거듭제곱을 사용한 while문으로 바꿔주기만 하면 된다.

 

warning) j를 0부터 올라가게 하면, 갱신이 무한히 되기 때문에 내려가게 구현해야 한다.

---

End

2진법, 2진수 같은 게 갈수록 중요해지는 것 같다. 비트마스킹? 같은 것도 2진법과 관련된 알고리즘이라고 알고 있는데,  나중에 찾아봐야겠다.

---