양팔 저울과 각각 무게가 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 이다.
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기
'강의자료 > 이산수학문제풀이' 카테고리의 다른 글
[사고력수학]수열에서 2의 배수와 3의 배수를 제거하기 (11) | 2024.02.07 |
---|---|
[검단코딩-정보올림피아드2023초등부]3. 거짓말(5점) (8) | 2024.02.02 |
[검단코딩-사고력 수학] 짧은 길의 경로 찾기 (17) | 2024.01.30 |
[검단코딩-정보올림피아드2023초등부]1. 자율주행(5점) (13) | 2024.01.29 |
[검단코딩-사고력 수학] 구슬 꺼내기 (12) | 2024.01.23 |