문제해설

특별한 알고리즘이 없는 시뮬레이션 문제이다. 먼저 한 톱니바퀴의 톱니가 8개 이므로 톱니바퀴의 개수만큼 크기가 8인 배열을 2차원 배열로 선언한다. (톱니바퀴 개수가 T개이므로 gear[T][8])
그 후 한 개의 톱니바퀴를 돌릴때마다 모든 톱니바퀴를 조건에 맞게 갱신해주면된다. 여기서 2가지 정도 고려를 해야한다.

각각의 톱니바퀴를 순차적으로 돌리지 말고 모든 톱니바퀴를 한번에 돌린다.

예를 들어 1, 2, 3 번 톱니바퀴가 있고 1번을 시계방향으로 돌리는 경우에 2번에 반시계 방향으로 돌아가고, 2번이 반시계로 방향으로 돌아가면 3번이 시계방향으로 돌아간다고 가정해보자.

이런경우 다음과 같이 동시에 톱니바퀴가 움직여야 한다. 하지만 한 개씩 순차적으로 돌리도록 코드를 작성하면 1번 톱니바퀴의 상태가 바뀌어버리기 때문에 1번의 S와 2번의 S가 서로 맞물려 있게 되므로 2번 톱니바퀴가 안돌아가게 된다.

돌아가지 않는 톱니바퀴가 있다면 이후 모든 톱니바퀴는 돌아가지 않는다.

톱니바퀴가 돌지 않으면 다음 톱니바퀴도 돌지 않기때문에 톱니바퀴가 돌지 않는 시점에서 탐색을 종료하면 된다. 이 경우는 시간을 단축시키기 위한 사항이지 고려하지 않았을 경우 답이 틀리진 않는다.

배열에서 톱니바퀴의 가장 위쪽 톱니의 index를 0이라고 할 경우 가장 오른쪽의 index가 2, 가장 왼쪽의 index가 6 이므로 두 톱니바퀴를 비교할때 왼쪽의 2번 index와 오른쪽의 6번 index를 확인해 톱니를 돌릴지 말지 결정하면된다.

구현 순서는 첫번째 돌리는 톱니바퀴를 기준으로 왼쪽, 오른쪽을 모두 탐색해 돌아가는 톱니바퀴와 도는 방향을 체크 -> 모든 톱니바퀴의 상태를 한번에 변경 -> 톱니바퀴를 돌리는 횟수인 K 번 반복 -> 마지막 상태에서 모든 톱니바퀴의 0번 index를 더한다.

구현, 시뮬레이션

시간복잡도

한개의 톱니를 돌릴때 최악의 경우 모든 톱니가 다 돌면 T개의 톱니에 대해 방향을 저장하고, 한 개의 톱니바퀴가 돌아갈때 톱니의 개수가 8개 이므로 T + 8T 번의 연산이 필요하다. 이 루틴을 K번 반복하기 때문에 총 9T * K 의 연산으로 시간 복잡도는 O(T * K)이다. (T, K <= 1000)

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = null;

        int T, K, answer = 0;
        int gear[][];

        T = Integer.parseInt(br.readLine());
        gear = new int[T][8];
        for (int i = 0; i < T; i++) {
            String s = br.readLine();
            for (int j = 0; j < 8; j++) {
                gear[i][j] = (s.charAt(j) - '0');
            }
        }

        K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int num, turn[] = new int[T];
            num = Integer.parseInt(st.nextToken()) - 1;
            turn[num] = Integer.parseInt(st.nextToken());

            for (int j = num; j < T - 1; j++) {
                if (gear[j][2] != gear[j + 1][6]) turn[j + 1] = turn[j] * -1;
                else break;
            }

            for (int j = num; 0 < j; j--) {
                if (gear[j][6] != gear[j - 1][2]) turn[j - 1] = turn[j] * -1;
                else break;
            }

            for (int j = 0; j < T; j++) {
                if (turn[j] == -1) {
                    int temp = gear[j][0];
                    for (int k = 0; k < 7; k++) {
                        gear[j][k] = gear[j][k + 1];
                    }
                    gear[j][7] = temp;
                }
                else if (turn[j] == 1) {
                    int temp = gear[j][7];
                    for (int k = 7; 0 < k; k--) {
                        gear[j][k] = gear[j][k - 1];
                    }
                    gear[j][0] = temp;
                }
            }
        }

        for (int i = 0; i < T; i++) {
            answer += gear[i][0];
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}