반응형
하노이의 탑
-
프로그래머스 Lv.3) 하노이의 탑알고리즘/프로그래머스 2020. 5. 31. 22:07
하노이의 탑 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대�� programmers.co.kr 풀이 문제에서 n이 15이하로 주어졌기 때문에, 메소드 재귀 호출을 이용해 문제를 풀어야겠다는 생각을 했다. 그리고, 문제 조건을 쭉 써본 결과 n에 대해 최소 이동 횟수는 2^n -1이 된다는 것을 파악했다. 우선, 최소 이동 횟수만큼 result 배열을 만들어 주었다. ( 0 : 원판을 가져온 기둥, 1 : 원판을 옮긴 기둥을 저장해야하기 때문에 2차원 배열) 그리고 이리저리 삽질을 한 것 같다. 재귀로 풀었지만 몇개 ..