[검단코딩-정보올림피아드2023초등부]2.양팔저울(5점)

양팔 저울과 각각 무게가 2kg,5kg,8kg인 추 3개와 빈 물통이 있다. 빈 물통의 무게는 0kg이며 물을 담을 수 있는 용량 제한은 없다.

양팔 저울을 한번만 이용하여 15kg 이하의 각 정수 무게에 해당하는 물을 물통에 담으려고 한다. 담을 수 없는 무게는 무엇인가?(각 무게에 해당하는 추는 1개 밖에 없고 추를 양팔 저울의 어느 쪽에도 놓을 수 있다는 것에 유의하라)

 

정답)

4kg,9kg,12kg,14kg

문제풀이)

양팔 저울을 어느 쪽에도 놓을 수 있다면 추의 차이만큼도 가능하다.

이것은 동적 알고리즘으로 해결이 가능한데 다음과 같은 원리이다.

0KG은 무조건 담을 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1

 

여기서 2kg 추가 주어진다면 2kg 과 |-2|kg 을 구할 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1		2

 

다음으로 5kg 이 주어진다면 0kg에서 +/- 5kg  2kg에서 +/- 5kg 이므로 5,3,7 을 구할 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1		2	3		3		3

 

다음으로 8kg 이 주어진다면 0kg +/- 8kg, 2kg +/- 8kg,  3kg +/- 8kg, 5kg +/- 8kg, 7kg +/- 8kg

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	4	2	3		3	4	3	4		4	4		4		4

여기서 숫자 1,2,3,4 는 단순히 순서를 의미한다. x와 같이 마킹을 하여도 상관 없다. 

 

따라서 담을 수 없는 무게는 4kg,9kg,12kg,14kg 이다.