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)
참고 링크
- http://acm.uva.es/p/v100/10026.html
- http://secuprint.tistory.com/entry/구두-수선공-문제-프로그래밍-챌린지
- http://www.4four.us/article/2010/03/shoemakers-problem // 처음 내가 겪었던 문제를 이 블로그에서도 똑같이 겪는다.
간략한 이야기
프로그램의 입/출력
생략
맛보기 사진
맛보기 코드
여담
- 처음에는 선택했을 때, 제일 벌금을 적게 낼 경우의 주문을 먼저 처리 했는데, 틀렸다. 왜냐하면, 총 벌금의 최소량과 관계가 없기 때문이다. (근접하게 갈 수는 있으나, 최소량은 아니다.)
- 그래서 전략을 벌금을 제일 많이 내야 할 주문부터 처리했다.
- 이 문제의 알고리즘 생각이 잘 떠오르지 않아, 백트래킹(모든 경우의 수)로 풀려고 했으나, 주문의 량이 많으면 많을 수록 몹시 느려지기 때문에, 써먹을 수 없는 방법이라고 생각해서 그만 뒀다.
- 다른 사람이 푼 방법을 보면, 좀 다른 방법을 쓰는데, 나는 각 요소의 연관관계를 잘 만들지 못해, 거기까지 생각하지 못했다.
:wq!
'책 정리 > Programming Challenges : 알고리즘 트래이닝 북' 카테고리의 다른 글
문제 34, 뒤집어서 더하기, Reverse and Add, PC/UVa ID : 110502/10018, 인기도 : A, 성공률 : 낮음, 레벨 : 1 (0) | 2011.03.10 |
---|---|
문제 33, 자리 올림, Primary Arithmetic, PC/UVa ID : 110501/10035, 인기도 : A, 성공률 : 보통, 레벨 : 1 (0) | 2011.03.10 |
문제 32, 축구, Football aka Soccer, PC/UVa ID : 110408/10194 (0) | 2011.03.02 |
문제 31, 셸 정렬, ShellSort, PC/UVa ID : 110407/10152 (0) | 2011.02.26 |
문제 30, CDVII, PC/UVa ID : 110406/10138 (0) | 2011.02.22 |
문제 28, 낮잠 오래 자기, Longest Nap PC/UVa ID : 110404/10191 (0) | 2011.02.10 |
문제 27, 다리, Bridge, PC/UVa ID : 110403/10037 (0) | 2011.02.08 |
문제 26, 팬 케이크, Stacks of Flapjacks, PC/UVa ID : 110402/120 (0) | 2011.02.01 |
문제 25, 비토와 친척들(Vito's Family), PC/UVa ID : 110401/10041 (0) | 2011.01.30 |
문제 24, Fmt, PC/UVa ID : 110308/848 (0) | 2011.01.30 |
최근댓글