[BaekJoon/C++] 14891번 톱니바퀴

14891번 백준 - 톱니바퀴

 

문제 링크: https://www.acmicpc.net/problem/14891

 

 

덱을 이용해서 풀었다.

분명 예제 입출력은 다 맞게 나오는데 계속 틀렸습니다!가 뜨길래 뭐지? 했는데 해답을 찾았다. 

회전시킬지 말지 & 어느 방향으로 회전시킬지 정보를 미리 저장해둔 후에 움직여야 한다!

그러지 않고 입력 받는 즉시 차례대로 움직이게 되면 비교하는 인덱스가 달라지기 때문!!!

 

 

<계속 틀렸던 코드>

아래는 내가 처음 제출한 코드다. 코드를 아주 비효율적으로 짠 걸 확인할 수 있는 건 덤이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<deque>

using namespace std;
#define MAX 51

int main() {
   vector<deque<int>> dq(4, deque<int>(8));
   int n;
   int a, b;
   char input[9]; // 문자 배열로 입력 받기 위한 배열

   for (int i = 0; i < 4; i++) {
      cin >> input; // 문자열로 톱니바퀴 상태 입력 받음
      for (int j = 0; j < 8; j++) {
         dq[i][j] = input[j] - '0'; // 문자 '0' 또는 '1'을 정수 0 또는 1로 변환하여 저장
      }
   }

   cin >> n;
   for (int i = 0; i < n; i++) {
      cin >> a >> b;
      if (a == 1) {
         if (b == 1) {
            if (dq[0][2] != dq[1][6]) { //a=0일 경우에는 dq[1]와 다른 극이어야지 2,3도 움직임
               dq[1].push_back(dq[1].front());
               dq[1].pop_front();

               if (dq[1][2] != dq[2][6]) {
                  dq[2].push_front(dq[2].back());
                  dq[2].pop_back();

                  if (dq[2][2] != dq[3][6]) {
                     dq[3].push_back(dq[3].front());
                     dq[3].pop_front();
                  }
               }
            }
            dq[0].push_front(dq[0].back());
            dq[0].pop_back();
            //여기서 0을 시계 방향으로 돌려줌
         }
         if (b == -1) {
            if (dq[0][2] != dq[1][6]) { //0일 경우에는 dq[1]과 다른 극이어야지 2,3도 움직임
               dq[1].push_front(dq[1].back());
               dq[1].pop_back();

               if (dq[1][2] != dq[2][6]) {
                  dq[2].push_back(dq[2].front());
                  dq[2].pop_front();

                  if (dq[2][2] != dq[3][6]) {
                     dq[3].push_front(dq[3].back());
                     dq[3].pop_back();
                  }
               }
            }
            dq[0].push_back(dq[0].front());
            dq[0].pop_front();
         }
         //여기서 1을 반시계 방향으로 돌려줌
      }

      if (a == 2) { //1일 경우, dq[2]과 다른 극이어야지 3도 움직임
         if (b == 1) {
            if (dq[0][2] != dq[1][6]) {
               dq[0].push_back(dq[0].front());
               dq[0].pop_front();
            }
            if (dq[1][2] != dq[2][6]) {
               //여기서 2 바뀌고
               dq[2].push_back(dq[2].front());
               dq[2].pop_front();

               if (dq[2][2] != dq[3][6]) {
                  dq[3].push_front(dq[3].back());
                  dq[3].pop_back();
               }
            }
            dq[1].push_front(dq[1].back());
            dq[1].pop_back();
         }
         if (b == -1) {
            if (dq[0][2] != dq[1][6]) {
               dq[0].push_front(dq[0].back());
               dq[0].pop_back();
            }
            if (dq[1][2] != dq[2][6]) {
               //여기서 2 바뀌고
               dq[2].push_front(dq[2].back());
               dq[2].pop_back();

               if (dq[2][2] != dq[3][6]) {
                  dq[3].push_back(dq[3].front());
                  dq[3].pop_front();
               }
            }
            dq[1].push_back(dq[1].front());
            dq[1].pop_front();
         }
      }


      if (a == 3) { //2일 경우, dq[1]와 다른 극이어야지 0도 움직일 수 있음
         if (b == 1) {
            if (dq[1][2] != dq[2][6]) {
               //여기서 1 바뀌고
               dq[1].push_back(dq[1].front());
               dq[1].pop_front();
               if (dq[0][2] != dq[1][6]) {
                  dq[0].push_front(dq[0].back());
                  dq[0].pop_back();
                  //0과 비교하면서 0이랑도 다른 극이면 도 바뀌는 것
               }
            }
            if (dq[2][2] != dq[3][6]) {//여기서는 2 & 3 비교
               dq[3].push_back(dq[3].front());
               dq[3].pop_front();
            }
            dq[2].push_front(dq[2].back());
            dq[2].pop_back();
         }
         if (b == -1) {
            if (dq[1][2] != dq[2][6]) {
               //여기서 1 바뀌고
               dq[1].push_front(dq[1].back());
               dq[1].pop_back();
               if (dq[0][2] != dq[1][6]) {
                  dq[0].push_back(dq[0].front());
                  dq[0].pop_front();
                  //0과 비교하면서 0이랑도 다른 극이면 0도 바뀌는 것
               }
            }
            if (dq[2][2] != dq[3][6]) {//여기서는 2 & 3 비교
               dq[3].push_front(dq[3].back());
               dq[3].pop_back();
            }
            dq[2].push_back(dq[2].front());
            dq[2].pop_front();
         }
      }

      if (a == 4) { //3일 경우, dq[2]과 다른 극이어야지 1,0도 움직일 수 있음
         if (b == 1) {
            if (dq[2][2] != dq[3][6]) {
               //여기서 2랑 비교
               dq[2].push_back(dq[2].front());
               dq[2].pop_front();
               if (dq[1][2] != dq[2][6]) {
                  dq[1].push_front(dq[1].back());
                  dq[1].pop_back();

                  if (dq[0][2] != dq[1][6]) {
                     dq[0].push_back(dq[0].front());
                     dq[0].pop_front();
                  }
               }
               dq[3].push_front(dq[3].back());
               dq[3].pop_back();
            }
         }
         if (b == -1) {
            if (dq[2][2] != dq[3][6]) {
            
               dq[2].push_front(dq[2].back());
               dq[2].pop_back();
               if (dq[1][2] != dq[2][6]) {
                  dq[1].push_back(dq[1].front());
                  dq[1].pop_front();

                  if (dq[0][2] != dq[1][6]) {
                     dq[0].push_front(dq[0].back());
                     dq[0].pop_back();
                  }
               }
               dq[3].push_back(dq[3].front());
               dq[3].pop_front();
            }
         }
      }
   }
   int ans = 0;
   if (dq[0][0] == 1) ans += 1;
   if (dq[1][0] == 1) ans += 2;
   if (dq[2][0] == 1) ans += 4;
   if (dq[3][0] == 1) ans += 8;

   cout  << ans << endl;  

   return 0;
}

 

 

<정답 처리된 코드>

isChange 는 회전시킬지 말지 여부를 저장하고, dir는 어느 방향으로 (1 or -1) 회전시킬지를 저장하는 벡터다.

위에서는 매우매우 비효율적으로 코드를 짰지만 아래 코드에서는 for 반복문으로 묶어줬다. 

#include<iostream>
#include<vector>
#include<deque>
#include<algorithm>
#include <string>

using namespace std;

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector <deque<int>>dq(4, deque<int>(8));

	string s;
	int n, a, b;
	for (int i = 0; i < 4; i++) {
		cin >> s;
		for (int j = 0; j < 8; j++) {
			dq[i][j] = s[j] - '0';
		}
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		a -= 1;
		vector<bool> isChange(4, false);
		vector<int> dir(4, 0);

		isChange[a] = true;
		dir[a] = b;

		for (int j = a; j > 0; j--) {
			if (isChange[j] && dq[j][6] != dq[j - 1][2]) {
				isChange[j - 1] = true;
				dir[j - 1] = -dir[j];
			}

		}
		for (int j = a; j < 3; j++) {
			if (isChange[j] == true && dq[j][2] != dq[j + 1][6]) {
				isChange[j + 1] = true;
				dir[j + 1] = -dir[j];
			}

		}
		for (int j = 0; j < 4; j++) {
			if (isChange[j] == true) {
				if (dir[j] == 1) {
					dq[j].push_front(dq[j].back());
					dq[j].pop_back();
				}
				else if (dir[j] == -1) {
					dq[j].push_back(dq[j].front());
					dq[j].pop_front();
				}
			}
		}
	}
	int ans = 0;
	if (dq[0][0] == 1) ans += 1;
	if (dq[1][0] == 1) ans += 2;
	if (dq[2][0] == 1) ans += 4;
	if (dq[3][0] == 1) ans += 8;

	cout << ans << "\n";

	return 0;
}