행복한 프로그래밍 > 다리 건너기
'행복한 프로그래밍' 에서 소개 되었던 최단 시간 다리 건너기 문제를 알고리즘으로 풀어 보았다. 문제 : 갑, 을, 병, 정이라는 사내 네 명이 밤에 다리를 건너려고 한다. 다리는 한 번에 두 사람까지만 건널 수 있다. 손정등이 있어야만 다리를 건널 수 있다. 갑이 다리를 건너는 데에는 1분이 걸리고, 을은 2분, 병은 5분 그리고 정은 10분이 걸린다. 두 사람이 다리를 건널 때는 느린 사람, 즉 시간이 더 많이 걸리는 사람에게 맞춰서 건너가야 한다. 에를 들어서 을 과 정이 다리를 건널 때 걸리는 시간은 2분이 아니라 10분이다. 자, 사내 네명이 모두 다리를 건너가는 데 걸리는 가장 짧은 시간은 몇 분인가? 답 : 17분 풀이 : 처음 출발 할때 갑,을,병,정 중에 가장 빠른 두 사람이 출발한다. ..
2021. 7. 28.