문제 링크

https://www.acmicpc.net/problem/14891

문제 설명

• 자석 8개가 달린 톱니바퀴 4개 주어짐
• 어떤 톱니바퀴를 어느 방향으로 돌릴지 순서가 주어짐
• 어떤 바퀴를 시계 방향으로 돌릴 때 맞물리는 자석의 극이 다르면 같이 돌아감
• 순서대로 돌린 후 점수 계산하여 리턴

풀이

• 재귀로 구현
• 점화식
  • 현재 톱니바퀴 visited = True
  • 왼쪽 맞으면 재귀적으로 돌리기
  • 오른쪽 맞으면 재귀적으로 돌리기
  • 현재 톱니바퀴 돌리기

코드

def turn(turned, i, d):
    turned[i] = True
    # 왼쪽 맞으면
    if i-1 >= 0 and not turned[i-1] and wheels[i-1][2] != wheels[i][6]:
        turn(turned, i-1, -d)
    # 오른쪽 맞으면
    if i+1 <= 3 and not turned[i+1] and wheels[i][2] != wheels[i+1][6]:
        turn(turned, i+1, -d)
    wheels[i].rotate(d)


# init
from collections import deque
import sys
read = sys.stdin.readline
wheels = [deque(map(int, read().rstrip())) for _ in range(4)]
k = int(read())
orders = [list(map(int, read().split())) for _ in range(k)]

# start
for num, d in orders:
    turned = [False] * 4
    turn(turned, num - 1, d)
print(sum([wheels[i][0] * (2 ** i) for i in range(4)]))