https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
자료구조 수업시간에 재귀를 배울 때 나온 내용
배우고 시험봤을때는 쉬웠는데 한달 동안 쉬고 봤더니 은근 까다로움
알고리즘
1번에서 3번으로 n개의 원판을 옮긴다고 하자
그렇다면 가장 큰 판을 3번으로 우선 옮겨야 할 것이다.
따라서 가장 큰 판을 제외하고 n-1개의 나머지 판들을 2번으로 옮긴다.
그리고 가장 큰 판을 3번으로 옮긴 후 2번의 n-1개 판들을 3번으로 옮기면 된다.
나머지 판에 대해서도 재귀로 반복하면 된다. (이것은 직접 써보면서 해야지 이해가 됨)
코드
두가지로 풀 수 있다.
하노이 탑을 움직이는 것은 똑같다.
그러나 하노이 탑이 움직이는 횟수를 먼저 출력해야 되기 때문에 두가지로 풀 수 있다.
1.
첫번째는 h_count라는 하노이 탑이 움직이는 횟수를 세는 함수를 만든다.
이 함수는 하노이 탑이 움직이는 알고리즘과 같다.
h_count의 첫부분에 count를 증가시킨다.
2.
두번재는 하노이 탑이 최소로 움직이는 횟수는 2^n-1이다.
따라서 math.h를 포함시켜서 pow함수를 이용해 2^n-1을 먼저 출력시키면 된다.
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
자료구조 수업시간에 재귀를 배울 때 나온 내용
배우고 시험봤을때는 쉬웠는데 한달 동안 쉬고 봤더니 은근 까다로움
알고리즘
1번에서 3번으로 n개의 원판을 옮긴다고 하자
그렇다면 가장 큰 판을 3번으로 우선 옮겨야 할 것이다.
따라서 가장 큰 판을 제외하고 n-1개의 나머지 판들을 2번으로 옮긴다.
그리고 가장 큰 판을 3번으로 옮긴 후 2번의 n-1개 판들을 3번으로 옮기면 된다.
나머지 판에 대해서도 재귀로 반복하면 된다. (이것은 직접 써보면서 해야지 이해가 됨)
코드
두가지로 풀 수 있다.
하노이 탑을 움직이는 것은 똑같다.
그러나 하노이 탑이 움직이는 횟수를 먼저 출력해야 되기 때문에 두가지로 풀 수 있다.
1.
첫번째는 h_count라는 하노이 탑이 움직이는 횟수를 세는 함수를 만든다.
이 함수는 하노이 탑이 움직이는 알고리즘과 같다.
h_count의 첫부분에 count를 증가시킨다.
2.
두번재는 하노이 탑이 최소로 움직이는 횟수는 2^n-1이다.
따라서 math.h를 포함시켜서 pow함수를 이용해 2^n-1을 먼저 출력시키면 된다.
