더블릿
수(기타) 놀이터 | 문제 코너 | 제출 현황 | 수학 Q/A | 수학 quiz |

koi table 대회 풀이

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

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



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


  점화식은 다음과 같다.

    

        

      


       


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


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


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


1970:01:01 .. written by testid...[질/답]