PC/UVa ID : 110403/10037

이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • firefox4 beta10
  • eclipse 3.6.1 + vrapper
  • lua 5.1.4

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 27, 다리, Bridge, page 123)

참고 링크

이야기

n명의 사람들이 밤중에 늑대들에게 쫒기고 있다. 강 위에 있는 다리를 건너면, 안전하게 늑대들을 피할 수 있다. 밤 중엔 다리를 건너기 위해서 플래시를 이용해 건너야 한다. 다리는 최대 두명이 동시에 건널 수 있으며, 플래시는 한개밖에 없다. 그래서 두 명이 다리를 건너면 그 중 한명은 플래시를 가지고 되돌아 와야 한다.

또한 사람마다 다리를 건너는 속도가 다른데, 두명이 다리를 건널 땐, 제일 느린 사람 기준으로 다리를 건너야 한다.

자, 이제 살아남기 위해, 제일 빠른 시간에 다리를 건너는 방법을 출력하여라.

프로그램의 입/출력

  1. 늘 그렇듯 테스트 케이스를 정수로 입력 받고, 입력 받은 뒤 한 라인 공백을 준다.
  2. 사람 수를 입력 받고 다음 라인엔 그 사람 수 만큼 라인 단위로 한명씩 속도로 입력 받는다.

  3. 입력이 끝나는 데로 제일 빠른 시간에 다리를 건너는 방법을 출력하고, 테스트 케이스 만큼 반복한다.
  4. 자세한 사항은 맛보기 사진을 볼것

맛보기 사진

맛보기 코드

여담

  • 나도 두개의 시나리오를 생각 했으나, 두개의 시나리오를 결합하여 최적의 값을 유추한다는 생각은 못했었다.
  • 두개의 시나리오를 결합하는 생각과 수학적으로 결합하는 방법에 큰 감동을 받았다.

  • 유닛 테스트가 있기 때문에, 버그도 엄청나게 쉽게 찾을 수 있었다. TDD는 정말 뛰어난 개발 방법론이다.

  • 알고리즘의 관건은 제일 느린 사람을 제일 빠른 방법으로 건너게 하는 것이다. (결론적으로 제일 빠른 방법이다.)

:wq!

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요