문제 25, 비토와 친척들(Vito's Family), PC/UVa ID : 110401/10041

PC/UVa ID : 110401/10041

이 포스트를 만든 목적

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

이 포스트의 준비물

• firefox4 beta10
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

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

참고 링크

• http://acm.uva.es/p/v100/10041.html - 문제 원문

이야기

비토가 친척들이 있는 뉴욕으로 이사를 가는데, 친척들과 자주 만나기 위해 친척들과 가까운 곳에 집을 구해야 한다. 비토는 모든 친척들 집과 거리 총합이 제일 작은 곳에 이사를 가야 한다.  비토는 프로그래머인 당신을 납치하여, 프로그램을 만들어 달라고 협박을 한다.

프로그램의 입/출력

1. 최초 프로그램은 여러개의 테스트 케이스를 입력받을 수 있게 양의 정수를 입력 받는다.
   
2. 각 테스트 케이스 마다 친척집의 수를 나타내는 정수 0 < r < 500 사이의 수와
   친척들의 번지수를 나타내는 정수를 입력 받는데, 0 < s < 30,000 사이의 수를 입력받는다.
   
   
3. 입력이 끝나는데로, 비토의 집과 각 친척들 집과의 거리의 총합을 출력 한다.
   

예외 상황

• 친척들 중에 같은 번지에 살고 있는 사람들도 있을 수 있다.
  

맛보기 코드

-- PC/UVa : 110401/10041 -- http://ikpil.com -- 2011.01.30 ------------------------------------------------------------------------------- function fn_vitos_the_nearest_location(tb_location) -- by average local total = 0 for k, v in pairs(tb_location) do total = total + v end return math.floor(total / #tb_location) --[[ -- by sort table.sort(tb_location) local center = math.ceil(#tb_location / 2) return tb_location[center] --]] end function fn_vitos_total_distance(tb_location, nearest) local total_distance = 0 for k, v in pairs(tb_location) do total_distance = total_distance + math.abs(v - nearest) end return total_distance end function main() local case = io.read("*line") case = case - 0 for i = 1, case do local line = io.read("*line") local tb_location = {} local parser = line:gmatch("%d+") for ii = 1, parser() do tb_location[ii] = parser() end local nearest = fn_vitos_the_nearest_location(tb_location) local total_distance = fn_vitos_total_distance(tb_location, nearest) print(total_distance) end end main()

맛보기 사진

여담

• 문제를 다르게 풀면, 더 쉽게 말해서, 평균과 각 편차들간의 합을 구하는 문제이다.
  
• 그래서 정렬로도 풀어 보고, 평균으로도 풀어 봤다.
  
  
• TDD(테스트 주도 개발)방법론 으로 문제를 풀고 있는데, 괜찮다.
  

:wq