Bridge

https://codefights.com/challenge/K4HYozLrbRoLHkt8P

Author

peltorator

3000

You and your friends like to party but all the party spots are across the bridge from where you guys live. The bridge is quite old and unsafe, so only two people at a time can cross it and they need a lamp to do so at night. Unfortunately, your group only has one lamp.

This particular night is very cold, so you want everyone to cross the bridge as fast as possible. For the ithperson in your group you know the time ti it will take them to cross the bridge. When two people i and jcross the bridge, they walk at the speed of the slowest of them, so it would take max(ti, tj) to get to the other side.

Calculate the minimal time your group will need to cross the bridge.

Example

For t = [1, 2, 5, 10], the output should be
Bridge(t) = 17.

어릴 때 부터 IQ 테스트 같은데서 많이 보던 문제다. 늑대와 양, 나그네 등등 여러 변형판이 존재하는 문제다.

여러 명의 사람들이 다리를 건너가야하는데 각 사람들은 건너가는 시간이 있고, 두 사람씩만 건널 수 있으며, 램프가 있어 최소 한 사람은 다시 돌아오기 위해 다리를 이동해야한다. 여기서 최소한의 이동 시간을 찾는 문제다.

건너가는데 각각 1시간, 2시간, 5시간, 8시간이 걸리는 사람 A, B, C, D 4명이 있다고 생각해보고 해결해보자.

가장 처음으로 떠오르는 생각은 '어차피 누군가는 계속해서 돌아와야 하니 이 시간을 최소화시켜야 한다.' 그러므로 가장 빨리 다리를 건너는 (여기서는 A) 사람 한명이 계속해서 한사람씩을 데려가고 다시 돌아오는 것이다.

이렇게 하면 2+5+8 [A와 다른 사람들이 같이가는 시간] 에다가 1 + 1 [A혼자서 다시 오는 시간]

다 더해서 17분.

꺼림칙한가? 그럴만하다. 틀렸다.

문제는 C,D와 같이 오래 걸리는 사람들을 계속해서 왔다갔다 거리면서 시간을 낭비하는 데 있다.

만약에 C,D를 한꺼번에 보낸다면 왔다갔다 하는 시간을 크게 줄일 수 있는 것이다.

- 참조

http://page.mi.fu-berlin.de/rote/Papers/pdf/Crossing+the+bridge+at+night.pdf  (알고리즘에 대한 문서)

https://en.wikipedia.org/wiki/Bridge_and_torch_problem