양팔 저울과 각각 무게가 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..
