알고리즘/BOJ

백준 14891번 톱니바퀴

꾸준함. 2019. 3. 9. 22:40

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


동기의 요청으로 풀어본 문제인데 꽤나 재밌는 문제였습니다.

저는 덱을 이용하여 시뮬레이션을 돌려 풀었는데 조세퍼스 문제처럼 인덱스를 모듈러 연산을 하며 풀어도 될 법한 문제였습니다.


#include <iostream>

#include <string>

#include <deque>

#include <queue>

#include <cmath>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

 

        deque<int> dq[5];

        for (int i = 1; i < 5; i++)

        {

                 string s;

                 cin >> s;

 

                 for(int j=0; j<s.length(); j++)

                         dq[i].push_back(s[j] - '0');

        }

 

        int K;

        cin >> K;

        for (int i = 0; i < K; i++)

        {

                 int num, dir;

                 cin >> num >> dir;

 

                 int idx = num;

                 int tempDir = dir;

                 queue<pair<int, int>> q;

                 q.push({ idx, tempDir });

 

                 //check right

                 while (1)

                 {

                         if (idx == 4)

                                 break;

 

                         idx++;

                         tempDir *= -1;

                         if (dq[idx - 1][2] != dq[idx][6])

                                 q.push({ idx, tempDir });

                         else

                                 break;

                 }

 

                 idx = num;

                 tempDir = dir;

                 //check left

                 while (1)

                 {

                         if (idx == 1)

                                 break;

 

                         idx--;

                         tempDir *= -1;

                         if (dq[idx + 1][6] != dq[idx][2])

                                 q.push({ idx, tempDir });

                         else

                                 break;

                 }

 

                 //rotate the magnet

                 while (!q.empty())

                 {

                         int cur = q.front().first;

                         int rotate = q.front().second;

                         q.pop();

 

                         //clockwise

                         if (rotate == 1)

                         {

                                 int temp = dq[cur].back();

                                 dq[cur].pop_back();

                                 dq[cur].push_front(temp);

                         }

                         //anti clockwise

                         else

                         {

                                 int temp = dq[cur].front();

                                 dq[cur].pop_front();

                                 dq[cur].push_back(temp);

                         }

                 }

        }

 

        int result = 0;

        for (int i = 1; i < 5; i++)

                 if (dq[i].front() == 1)

                         result += (int)pow(2, i - 1);

 

        cout << result << "\n";

        return 0;

}


개발환경:Visual Studio 2017


지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

반응형

'알고리즘 > BOJ' 카테고리의 다른 글

백준 10757번 큰 수 A+B  (7) 2019.03.15
백준 1850번 최대공약수  (0) 2019.03.15
백준 14490번 백대열  (0) 2019.03.07
백준 2164번 카드2  (0) 2019.03.07
백준 10773번 제로  (0) 2019.03.07