더블릿
30 계단 | 옥 상 | 제출 현황 | Ranking | FAQs | 오류보고 | QandA | 푼   후 | 자유게시판 |
 
koi table 대회 풀이
삭제 | 편집 | 답글

현재 세 가족 구성원들이 먹고 싶어 하는 리스트를 각각 A, B, C 라고 한다. 각 가족 구성원들이 정해진 음식 리스트 순서대로 음식을 먹어야하기 때문에, 동적계획법으로 해결이 가능하다.

점화식 항의 정의는 다음과 같다.



A 리스트에서 번째까지, B에서 , C에서 번째까지 가족 구성원들이 음식을 먹었을 때, 그리고  번째 가족 구성원이 마지막으로 음식을 먹었을 때 회전 테이블의 위치에 있을 때, 회전 테이블의 최소 회전량 ( = 1, 2, 3).


  점화식은 다음과 같다.

  •   A리스트에서 마지막으로 음식을 먹는 경우:

    

        

  •   B리스트에서 마지막으로 음식을 먹는 경우:

      


  •   C리스트에서 마지막으로 음식을 먹는 경우:

       


단, Cost는 테이블의 현재 위치에서 목표 위치까지 테이블을 옮기는 데 필요한 회전량이다. 


테이블의 현재 위치는   에서 를 이용해 추측할 수 있다. 

  •  인 경우, 테이블의 현재 위치는 A[a] 이다.  
  • 인 경우 두 번째 가족 구성원 앞에 이고,
  •  인 경우 세 번째 가족 구성원 앞에  이다. 즉, 테이블의 위치는 어떤 가족 구성원을 기준으로 어떤 음식이 앞에 있는지를 정하면 된다.


  최종 답은 A, B, C 모든 리스트의 음식을 먹었을 때 테이블의 최소 회전량이므로, 위 점화식의 정의에 의해 최종 답은   이고 이때의 시간복잡도는  이다.

 
2012-07-31 09:53 , testid
[previous]