이전 퀴즈 [quiz 45] 다리건너기 의 다른 버전이다.
4명의 남자가 한 밤중에 다리를 건너려고 한다.
이 다리에는 한번에 2명만 올라갈 수 있고, 다리가 위험하기 때문에 건널 때에는 손전등이 필요하고
함께 건너는 사람 중 느린 사람의 속도로 건너야 한다.
J 는 다리를 건너는데 1분이 걸리고, K 는 2분, R 는 5분 M 는 8분이 걸린다.
이 4명의 남자들이 어떻게 해야 16분 안에 무사히 다리를 건널 수 있을까?
손전등은 하나밖에 없고, 던질 수 없다.
이런 문제를 풀 때 많은 사람들이 착각 하는 방법은 다음과 같다. 바로 빠른 사람에만 초점을 맞추는것이다. 하지만 빠른 사람과 느린 사람이 같이 가면 결국에 느린 사람만큼 시간이 걸리고, 돌아가는 것이 빨라 보았자 결국에 빠른 사람은 항상 자기보다 느린 사람과 같이 가게 된다. 실제로 초점을 두어야 할 것은 빠른 사람을 많이 움직이게 하여 시간을 최소화 하는 것이 아니라 느린 사람을 최소로 움직이게 만든 것이다.
즉 이 문제의 핵심은 가장 느린 사람 둘을 같이 움직이게 하고 이들의 움직임을 최소화 하는 것이다.
느린사람 두명의 움직임을 어떻게 하면 최소화 할까? 느린 사람 그룹이 먼저 가게 되면 어떻게 될까? 갔다가 한명은 무조건 돌아와야 하는데 느린사람들 둘이 가면 돌아오는데 다른 느린 사람이 또 건너와야 한다. 그리고 이 사람 역시 결국엔 돌아와야 하기에 느린 사람 두명이 맨 처음에 가는 것은 매우 좋지 않다.
결국 우리가 하고 싶은 방법은 느린 두 사람을 같이 움직이되 돌아오는 것은 빠른 사람을 이용하는 것이다. 즉 처음에 빠른 두 사람을 보내고 그 다음에 느린 두 사람이 가고 다시 빠른 사람이 돌아오는 방식으로 느린 두 사람을 먼저 보내버리면 위 문제를 해결 할 수 있다.
문제의 상황으로 돌아가면 풀이는 다음과 같다.
J 와 K 가 먼저 건너고(2분)
K 가 손전등을 들고 다시 돌아온다 (2분)
R 과 M 이 함께 건너고 (8분)
J 가 돌아온다 (1분)
J 와 K 가 돌아온다. (2분)
총 걸린 시간은 2+2+8+1+2=15, 즉 15분이다.
한번의 다리에 3명을 옮기는 경우도 생각해 볼 수 있다. 이는 다리건너기-3 퀴즈에서 생각해보자.
