[#28][알고리즘] 하노이의 탑

프로그래머스 > 하노이의 탑

문제 링크(https://programmers.co.kr/learn/challenge_codes/157)

C++풀이

#include<iostream> #include<vector> #include<algorithm> using namespace std; vector<vector<int> > answer; void move(int no, int begin, int end){   if(no==1){       answer.push_back({begin, end});   }else{     int passPoint = 6 - begin - end;     move(no-1, begin, passPoint);     answer.push_back({begin, end});     move(no-1, passPoint, end);        } } vector<vector<int> > hanoi(int no) {     move(no,1,3);        return answer; } int main() {     int testNo = 2;     vector<vector<int> > testAnswer = hanoi(testNo);     // 아래는 테스트로 출력해 보기 위한 코드입니다.     for(int i=0; i< testAnswer.size(); i++)     {         for(int j=0; j<testAnswer[i].size(); j++)         {             cout << testAnswer[i][j] << " ";         }         cout << "\n";     } } Colored by Color Scripter

cs

N개의 원판

if (원판이 1개 있을 때)

 바로 막대 1 -> 막대 3으로 옮김

else

1. N-1개의 원판을 막대 2로 옮긴다.

2. 막대 1에 남아있는 가장 큰 원판을 막대 3으로 옮긴다.

3. STEP1에서 막대 2로 옮겨진 N-1개의 원판을 막대 3으로 옮긴다.

예) 2개의 원판이 있을 때

막대 1 -> 막대 2 (passPoint): 맨 위의 원판 옮김

막대 1 -> 막대 3 : 맨 아래의 원판 옮김

막대 2 (passPoint)-> 막대 3 : 막대 2로 옮겨진(처음에 맨 위에있던) 원판 옮김

답 => [[1,2], [1,3], [2,3]]