koosaga   6년 전

다리 4개 하노이는 효율적인 해결 방법이 알려지지 않은 open problem입니다.

https://en.wikipedia.org/wiki/Tower_of_Hanoi#With_...

아마 출제자 분이 위키 링크에 있는 Frame-Stewart Algorithm을 의도로 해서 출제하신 걸로 추정되는데, 이 알고리즘은 증명되지 않은 추측일 뿐이기 때문에, 이 알고리즘을 사용한 것은 문제를 해결했다고 보기 곤란합니다.

고로, 출제자 분이 어떻게 N <= 1000000 짜리 데이터를 만드셨는지가 관건인데, 이 부분을 검토해 주셨으면 ㅎ

koosaga   6년 전

ㅏ ㅂ니다.


ntopia   6년 전

네 koosaga님의 말이 맞습니다..

이 문제도 여기에 올라와있었다니..

ntopia   6년 전

이 문제 지워야되지 않을까..싶네요..ㅠㅠ

baekjoon   6년 전

https://en.wikipedia.org/wiki/Tower_of_Hanoi#With_... 를 사용하라고 문제에 적었습니다.

WeissBlume   4달 전

탑이 4개일 때 Frame–Stewart algorithm이 최적해를 준다는 것은 2014년에 증명되었습니다.

(https://www.acmicpc.net/board/...)

koosaga   4달 전

논문이 프랑스어이고 해당 논문이 Frame-Stewart Algorithm을 의미한 것인지 아니면 다른 Optimal Algorithm을 의미한 것인지 모르겠습니다.

Wayback machine으로 링크가 되어 있는데 피어 리뷰 받은 건지도 모르겠고요.

만약 힌트가 제거되려면 최소한 다시 검수를 거쳐야 하지 않을까요?

댓글을 작성하려면 로그인해야 합니다.