Hoon222y

https://www.acmicpc.net/problem/11729우리가 평소에 알고 있던 하노이 탑을 이동시키며 그 경로를 출력하는 문제이다. 처음 문제를 보았을때는 시뮬레이션 해보며 특정순서에는 특정 규칙에 따라 이동을 한다고 생각하였는데 .... 뭔가 삽질을 하는것 같았다. 해당문제는 분할정복, 즉 dnc로 접근을 해볼 수 있다. 해당 하노이의 탑에서 1번에서 3번으로 옮기려면 어떤 과정을 거쳐야 할까? n개의 탑을 옮기기 위해서는 먼저 1번부터 n-1번까지 2번으로 옮기고, n번째 탑을 3번으로 옮기고, 1부터 n-1개의 탑을 3번으로 옮기면 된다. 정리를 하자면 solve(n,x,y) 는 solve(n-1,x,6-x-y) 후 n번째 판을 3번으로 옮기고, solve(n-1,6-x-y,y) 를 해..