코딩 정복 가즈아~
Home
  • 분류 전체보기 (159)
    • 알고리즘 풀이 (149)
      • 프로그래머스 (89)
      • 백준 (59)
    • 취준 일기 (6)
    • 네트워크 정리 (1)
Home
  • 분류 전체보기 (159)
    • 알고리즘 풀이 (149)
      • 프로그래머스 (89)
      • 백준 (59)
    • 취준 일기 (6)
    • 네트워크 정리 (1)
블로그 내 검색

코딩 정복 가즈아~

(っ◔◡◔)っ ♥ 2021 취뽀하자!! ♥

  • 알고리즘 풀이/백준

    [11729] 하노이 탑 이동 순서(C++)

    2020. 4. 27.

    by. 데롱디롱

    728x90

     

    * 접근한 방법
    - 하노이탑 이동의 규칙성을 찾음

    - 하노이탑 개수에 따른 이동 횟수
       :  1개 => 1회,    2개 => 3회,    3개 => 7회,    · · ·    
          ☞ 2 * (n -1)의 하노이 이동 횟수 + 1

    즉, 하노이는 n-1개를 2번에 옮기고 n을 1번에서 3번으로 옮긴 후 다시 n-1개를 2번에서 3번을 옮기는 것과 같음

    hanoi(n - 1, from, to, by);
    path.push_back(make_pair(from, to));
    hanoi(n - 1, by, from, to);

    ex) 하노이 탑 4개는 
         1~3의 하노이를 2번자리에 옮긴 후 
         4번 하노이를 3번자리에 옮기고 
         또 다시 1~3의 하노이를 3번자리로 옮긴다.

     

    #include <iostream>
    #include <vector>
    using namespace std;
    
    vector<pair<int, int>> path;
    
    void hanoi(int n, int from, int by, int to)
    {
    	if (n == 1) 
    		path.push_back(make_pair(from, to));
    	else
    	{
    		hanoi(n - 1, from, to, by);
    		path.push_back(make_pair(from, to));
    		hanoi(n - 1, by, from, to);
    	}
    }
    
    int main() {
    	int n;
    	cin >> n;
    
    	hanoi(n, 1, 2, 3);
    	cout << path.size() << "\n";
    	for (int i = 0; i < path.size(); i++)
    	{
    		cout << path[i].first << " " << path[i].second << "\n";
    	}
    }
    저작자표시 (새창열림)

    '알고리즘 풀이 > 백준' 카테고리의 다른 글

    [4949] 백준 : 균형잡힌 세상(C++)  (0) 2020.04.27
    [10773] 백준 : 제로(C++)  (0) 2020.04.27
    [2447] 백준 : 별 찍기 - 10(C++)  (0) 2020.04.26
    [1002] 백준 : 터렛(C++)  (0) 2020.04.26
    [3053] 택시 기하학(C++)  (0) 2020.04.26

    댓글

    관련글

    • [4949] 백준 : 균형잡힌 세상(C++) 2020.04.27
    • [10773] 백준 : 제로(C++) 2020.04.27
    • [2447] 백준 : 별 찍기 - 10(C++) 2020.04.26
    • [1002] 백준 : 터렛(C++) 2020.04.26
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

피할 수 없다면, 순간을 즐겨라

Designed by Nana
블로그 이미지
데롱디롱
희희.. (๑′ᴗ‵๑)

티스토리툴바