문제
승민이는 기존 하노이 탑 문제를 약간 변형한 이상한 하노이 탑 문제를 만들었다.
이상한 하노이 탑 문제와 기존 하노이 탑 문제와 다른 점이 2가지가 있는데 하나는 "쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.(중간 과정 역시 그래야함)" 라는 조건이 삭제되었다는 점이고 또 다른 하나는 첫 번째 장대에 원판들이 반경 상관없이 무작위로 배치되어 있다는 점이다.
승민이는 이 문제를 진수에게 주었고 원판을 옮긴 횟수가 12345보다 같거나 작으면 피자를 사주기로 하였다. 진수를 도와 피자를 먹게 해주자!
입력
첫 번째 줄에는 원판의 개수 N (1 ≤ N ≤ 123) 이 주어진다.
두 번째 줄에는 첫 번째 장대에 있는 원판들의 반경 나타내는 정수 ai (1 ≤ ai ≤ N) 들이 공백을 두고 주어진다. (제일 아래에 있는 원판의 반경부터 주어진다.)
출력
첫 번째 줄에 원판을 옮긴 횟수 K (0 ≤ K ≤ 12345) 를 출력한다.
다음 K 개 줄에 걸쳐 A B (1 ≤ A, B ≤ 3) 를 출력하는데 A 번째 장대 맨위에 있는 원판 하나를 B 번째 장대 맨위로 옮긴다는 뜻이다.
https://www.acmicpc.net/problem/15500
사라진 규칙덕분에, 구현해야할 동작이 단순해졌다.
우선 원판은 쌓아진 반대순서로 먼저 꺼내지므로, 3곳장대를 stack으로 구현하면된다.
처음 원판은 입력된순서대로 1번장대에 해당하는 stack에 넣고,
1번장대, 2번장대중에 큰 값을 가지는 장대의 원판을 stack에서 꺼내서 3번장대에 쌓아야될값(입력받은 원판갯수로, 3번장대에 옮길때마다 하나씩 줄이면된다.)과 일치할시 3번으로, 만약 불일치하면
1번장대에서 꺼낸것은 2번장대로, 2번에서 꺼낸것은 1번 장대로 옮기도록 구현하면된다.
마지막으로 출력이 좀 까다로운데, stack구조로보듯이, 매 순간마다 출력하면 역순으로 출력이 되므로, 처음에는 string문자열에 출력값을 저장하려고했다.
이렇게 처음 코드를 제출했으나..
반복되는 메모리초과... 여기에 이유를 찾아보니
1) 장대 3곳이아닌 1번장대 2번장대만 stack으로 구현하면된다.
-> 먼저, 3번장대에 원판을옮기는 순간을 기록하고나면, 우리는 3번장대에 더이상 관심을 안가져도된다. 이미 출력값만 기록하면 끝이니까.
2) string에저장하지않고 vector객체를 만들어서 출력값을 저장하면된다.
-> 이것이 가장 큰 문제였던것같은데, 이 부분구현에대해선 아래에서 자세히살펴보겠다.
그리고 구조를 바꿨는데, 1번장대에서 모든원판을 분배하고나면 2번장대에서 모든원판을 분배, 그리고 1번장대에서 모든원판을 분배.. 하는 방식으로 수정하였다.
최종적으로 제출하여 정답을 맞은 코드는 아래와 같다.
#include <iostream>
#include <stack>
#include <vector>
#include <utility>
using namespace std;
stack<int> s[3]; //기둥을 나타내는 스택
vector< pair<int, int> >result;
void move(int a, int b) {
int temp = s[a - 1].top();
s[a - 1].pop();
if (b != 3) s[b - 1].push(temp);
result.push_back({ a, b });
}
int main(void) {
int n, temp;
cin >> n;
int moveCnt = 0;
int currentDisk = n;
while (n--) {
cin >> temp;
s[0].push(temp);
}
bool right = true;
while (currentDisk > 0) {
int s1 = 0, s2 = 0;
if (right) { // 1번에서 2번,3번으로 옮긴다.
while(!s[0].empty()){ // 옮길것이 남아있다면
int temp = s[0].top();
if (temp == currentDisk) { // 현재 3번에 가야할원판이면
move(1, 3);
currentDisk--;
}
else {
move(1, 2);
}
}
if (s[0].empty()) right = false;
}
else { // 2번에서 1번,3번으로 옮긴다.
while (!s[1].empty()) {
int temp = s[1].top();
if (temp == currentDisk) {
move(2, 3);
currentDisk--;
}
else {
move(2, 1);
}
}
if (s[1].empty()) right = true;
}
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); i++)
cout << result[i].first << " " << result[i].second << endl;
return 0;
}move함수를 만들어서 코드의 중복을 피하고 출력값을 vector객체에 저장하게 하였다.
- vector클래스사용시 #include< vector>
- pair클래스 사용시 #include < utility>
- 선언시사용한 pair< int, int>는 pair클래스를 이용하여
두가지의 타입을 하나의 타입으로 관리할수 있게 해준다.
.first 와 .second로 지정한 타입의 값 출력 - #include < bits/stdc++.h>
표준 라이브러리는 아니나, 주로 사용하는 웬만한 헤더파일을 참조해놓은 헤더파일 (C 24개 / C++ 51개) 다운로드는 아래링크
https://drive.google.com/file/d/1bpjK-4Dt8a4kJMmbxqkHpDSn0vJb-Mh8/view?usp=sharing
이것을 받은다음에
설치된 VS폴더\2019\Community\VC\Tools\MSVC\숫자로되있음\include
에 bits폴더를 생성후 다운받은 헤더파일을 넣으면된다.
이제 사용시에 #include <bits/stdc++.h>
결국엔 풀었다.ㅎㅎ..
