https://www.acmicpc.net/problem/14891
14891번: 톱니바퀴
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴
www.acmicpc.net
문제는 8개의 톱니를 가지고 있는 톱니바퀴 4개를 회전시키는 문제다. 각 톱니는 N극 또는 S극을 가지고 있고 왼쪽 톱니바퀴부터 1번 2번 3번 4번이다. 톱니는 12시 방향을 기준으로 시계방향으로 인덱스를 부여한다. S극은 1로 N극은 0으로 나타낸다. 1번 톱니바퀴는 숫자 8자리로 나타내면 10101111이다.
따라서 회전할 경우 방향에 맞춰서 첫 번째 숫자를 pop 해서 뒤에 넣거나, 마지막 숫자를 빼서 앞으로 넣어야 하기 때문에 덱 자료구조를 사용했다. 그렇게 하면 첫 번째 혹은 마지막 원소의 삽입/삭제에 O(1) 이 걸리기 때문에 최대 회전 100번이라도 최악 상황의 톱니의 총회전은 400번이다.
이때 각각의 톱니바퀴는 시계방향 또는 반시계방향으로 N번 회전 가능하다. 또한 회전하는 경우 양 옆의 톱니바퀴의 극성에 따라서 양 옆의 톱니바퀴도 같이 회전한다. 만약 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다.
여기서 문제는 양 옆의 톱니바퀴에 영향을 주는 극성이 회전 한 뒤에 위치한 극성이 아니라, 원래 초기에 닿아 있던 극성이 영향을 준다는 것이다. 따라서 3번 톱니바퀴를 N번 돌리고 그다음 양 옆의 톱니의 극성을 확인해서 회전시키는 것이 아니다.
처음 문제를 풀 때는 회전을 먼저 하는 식으로 구현했지만 통과하지 못했다. 이후에 톱니바퀴를 회전하기 전에 만약 회전하면 영향을 받아 회전할 톱니를 그때그때 따로 배열에 방향과 톱니의 인덱스를 저장해 두고 마지막에 한 번에 회전시켰다.
import sys
from collections import deque
def rotation(list , dir):
if dir == 1:
last = list.pop()
list.appendleft(last)
else:
first = list.popleft()
list.append(first)
return list
g = []
for i in range(4):
s = deque()
cir = sys.stdin.readline().rstrip()
for j in cir:
s.append(int(j))
g.append(s)
k = int(sys.stdin.readline())
for i in range(k):
r = []
x,y = map(int,sys.stdin.readline().split())
r.append((x-1 , y))
sib = g[x-1] #현재 회전시킬 톱니의 옆 톱니 sibling
sibdir = y # sibling 톱니가 돌았던 방향 -1 또는 1
for j in range(x-2, -1, -1):
if sib[6] != g[j][2]: #12시 방향이 인덱스 0이므로 3시방향이 2, 9시방향이 6
sib = g[j]
sibdir = -sibdir
r.append((j,sibdir))
#g[j] = rotation(g[j], sibdir)
else:
break
sib = g[x-1]
sibdir = y
for K in range(x,4):
if sib[2] != g[K][6]:
sib = g[K]
sibdir = -sibdir
r.append((K,sibdir))
#g[K] = rotation(g[K], sibdir)
else:
break
for i,di in r:
rotation(g[i],di)
res = 0
for i in range(4):
res += g[i][0]* 2**i #점수가 S극일때 2의 제곱수만큼
print(res)
