PC/UVa ID : 110405/10026

이 포스트를 만든 목적

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

이 포스트의 준비물

  • firefox4 beta11
  • eclipse 3.6.1 + vrapper
  • lua 5.1.4

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 29 구두 수선공 문제, Shoemaker's Problem, page 126)

참고 링크

간략한 이야기

능력 있는 구두 수선공은 일을 정말 깔끔하게 한다. 이러한 구두 수선공에게 많은 일거리가 주어진다. 일이 지연됨에 따라, 구두 수선공은 벌금을 내겠다고 했다. 벌금은 구두 수선 시작일 전까지 지난 일수 만큼 얼마씩 내겠다고 했다. 제일 적게 벌금을 내는 일처리 순서를 알려 달라고, 프로그래머인 당신에게 문의 했다.

프로그램의 입/출력

생략

맛보기 사진


맛보기 코드

여담

  • 처음에는 선택했을 때, 제일 벌금을 적게 낼 경우의 주문을 먼저 처리 했는데, 틀렸다. 왜냐하면, 총 벌금의 최소량과 관계가 없기 때문이다. (근접하게 갈 수는 있으나, 최소량은 아니다.)
  • 그래서 전략을 벌금을 제일 많이 내야 할 주문부터 처리했다.

  • 이 문제의 알고리즘 생각이 잘 떠오르지 않아, 백트래킹(모든 경우의 수)로 풀려고 했으나, 주문의 량이 많으면 많을 수록 몹시 느려지기 때문에, 써먹을 수 없는 방법이라고 생각해서 그만 뒀다.

  • 다른 사람이 푼 방법을 보면, 좀 다른 방법을 쓰는데, 나는 각 요소의 연관관계를 잘 만들지 못해, 거기까지 생각하지 못했다.

:wq!

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

댓글을 달아 주세요