문제 29, 구두 수선공 문제, Shoemaker's problem, PC/UVa ID : 110405/10026

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 // 처음 내가 겪었던 문제를 이 블로그에서도 똑같이 겪는다.
  

간략한 이야기

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

프로그램의 입/출력

생략

맛보기 사진

맛보기 코드
-- PC/UVa : 110405/10026 -- Title : Shoemaker's Problem -- http://ikpil.com -- 2011.02.10 ------------------------------------------------------------------------------- function calculate_least_penalty(tb_orders) for i = 1, #tb_orders do tb_orders[i].index = i end local tb_sequence = {} for loop = 1, #tb_orders do -- 현재 상태에서 모든 벌금을 계산한다. local tb_penalty = {} for i = 1, #tb_orders do local tb_calculate = {tb_orders[i].index, 0} for ii = 1, #tb_orders do if i ~= ii then -- 제일 늦게 했을 때, 내야할 벌금을 구한다. tb_calculate[2] = tb_calculate[2] + (tb_orders[i][2] * tb_orders[ii][1]) end end tb_penalty[#tb_penalty+1] = tb_calculate end -- 벌금을 제일 많이 낼 수 있는 주문을 찾고, 그것 부터 처리함 table.sort(tb_penalty, function (a, b) return a[2] > b[2] end) tb_sequence[#tb_sequence+1] = tb_penalty[1][1] -- 해당 주문을 처리 했으니, 삭제 local index = 0 for i = 1, #tb_orders do if tb_orders[i].index == tb_penalty[1][1] then index = i break end end table.remove(tb_orders, index) end return tb_sequence end function main() local case_count = io.read("*line") case_cout = case_count + 0 print(); io.flush() for i = 1, case_count do local n = io.read("*line") n = n + 0 local tb_orders = {} while #tb_orders < n do local input_str = io.read("*line") local a, b = input_str:match("(%d+) (%d+)") tb_orders[#tb_orders+1] = { a + 0, b + 0 } end local tb_solve = calculate_least_penalty(tb_orders) print(table.concat(tb_solve, " ")) io.flush() end end main() --[[ path = package.path package.path = "C:\\Users\\ikpil\\Desktop\\programming_challenges\\?.lua" package.path = package.path .. ";" .. path require "lunit" test_case = lunit:new() function test_case:test_calculate_least_penalty() local tb_orders = {} tb_orders[#tb_orders+1] = { 3, 4 } tb_orders[#tb_orders+1] = { 1, 1000 } tb_orders[#tb_orders+1] = { 2, 2 } tb_orders[#tb_orders+1] = { 5, 5 } lunit:assert_true("2 1 3 4" == table.concat(calculate_least_penalty(tb_orders), " ")) end lunit:run() --]]

여담

• 처음에는 선택했을 때, 제일 벌금을 적게 낼 경우의 주문을 먼저 처리 했는데, 틀렸다. 왜냐하면, 총 벌금의 최소량과 관계가 없기 때문이다. (근접하게 갈 수는 있으나, 최소량은 아니다.)
  
• 그래서 전략을 벌금을 제일 많이 내야 할 주문부터 처리했다.
  
  
• 이 문제의 알고리즘 생각이 잘 떠오르지 않아, 백트래킹(모든 경우의 수)로 풀려고 했으나, 주문의 량이 많으면 많을 수록 몹시 느려지기 때문에, 써먹을 수 없는 방법이라고 생각해서 그만 뒀다.
  
  
• 다른 사람이 푼 방법을 보면, 좀 다른 방법을 쓰는데, 나는 각 요소의 연관관계를 잘 만들지 못해, 거기까지 생각하지 못했다.
  

:wq!