[c++] 백준 11729 - 하노이 탑 이동 순서(재귀 호출)

0. [c++] 백준  -

https://www.acmicpc.net/problem/

1. 풀이

처음 재귀호출을 활용하여서 코드를 완성하였는데, 시간초과가 발생하였다.

결과를 출력하는 부분이 재귀호출 안에 들어있었는데, 그로 인해서 시간초과가 발생한 듯 하다.

시간초과를 막기 위해서 출력하는 부분 vector<pair<int, int> > 에 넣어 따로 보관하였는데, 이렇게 하니 시간초과가 발생하지 않았다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<iostream>   using namespace std;   int Count = 1;   int moveCount(int N) {     int ret = 1;     for (int i = 1; i <= N-1; i++) {         ret *= 2;         ret += 1;     }     return ret; }   void move(int N, int x, int y) {     if (N > 1)          move(N - 1, x, 6 - x - y);       cout << x << " " << y << "\n";     if (N > 1)         move(N - 1, 6 - x - y, y); }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;     cout << moveCount(N) << endl;     move(N, 1, 3);       return 0; } Colored by Color Scripter

cs

2)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<iostream> #include<vector>   using namespace std;   //int Count = 1; vector<pair<int, int> > v;   //int moveCount(int N) { //    int ret = 1; //    for (int i = 1; i <= N-1; i++) { //        ret *= 2; //        ret += 1; //    } //    return ret; //}   void move(int N, int x, int y) {     if (N == 1)         v.push_back({ x,y });     else {         move(N - 1, x, 6 - x - y);         v.push_back({ x,y });         move(N - 1, 6 - x - y, y);     }          }   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       int N;     cin >> N;       move(N, 1, 3);     cout << v.size() << endl;     for (int i = 0; i < v.size(); i++)         cout << v[i].first << " " << v[i].second << "\n";       return 0; } Colored by Color Scripter

cs

3. 참고

구종만, 「프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략」, 인사이트, 2012, p.216~236.

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!