[BOJ] 14891 톱니바퀴

1. 문제

• 총 8개의 톱니를 가지고 있는 톱니바퀴 4개

  • 톱니의 N극은 0, S극은 1

• 톱니바퀴에는 번호가 매겨져 있음

  • 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번

• 톱니바퀴 A를 회전할 때,

  • 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전

  • 서로 맞닿은 톱니의 극이 같다면, B는 회전하지 않음

    

    • 입력:
      - 4줄에 걸쳐 각 톱니바퀴 상태 입력 (N극은 0, S극은 1, 12시방향부터 시계 방향 순서대로)
      - 회전횟수 K (1≤ K ≤ 100)
      - K개 줄 동안 회전시킨 방법
      - 각 방법은 두 개의 정수 :
      - 회전시킨 톱니바퀴 번호
      - 방향 (1: 시계방향, -1: 반시계 방향)

      ⇒ 톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, K번 회전시킨 이후에 네 톱니바퀴의 점수의 합?

    • 점수 계산

      • 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
      • 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
      • 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
      • 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

2. 풀이

• 회전한다 == “기준이 바뀐다”
  • 12시 방향을 나타내는 배열 top 을 활용 (4개의 톱니바퀴지만, 1번부터 처리하므로 길이를 5로 설정)
  • 시계 방향 : -1
  • 반시계 방향 : +1
• 주어진 회전 정보 마다 (회전 톱니바퀴 idx, 회전방향)
  • idx 톱니바퀴의 오른쪽과 왼쪽으로 나누어서, idx의 회전에 따라 회전하는 톱니들을 조사
    • idx 톱니와 거리가 홀수만큼 차이나는 톱니는 반대방향으로 회전, 짝수만큼 차이나는 톱니는 같은 방향으로 회전
    • 회전할 톱니들은 tlst 배열에 담아서 오른쪽 왼쪽 조사를 모두 마친 뒤 한번에 회전

3. 코드

N = 4

arr = [[0] * 8] + [list(map(int, input())) for _ in range(N)]
K = int(input())

top = [0] * (N+1)

for _ in range(K):
    idx, dr = map(int, input().split())     #dr : cw = 1, ccw = -1 
    tlst = [(idx, 0)]                       # => but when rotating, ccw has to add to top[idx], cw has to subtract
    
    # right side of idx wheel
    for i in range(idx + 1, N + 1):        
        if arr[i-1][(top[i - 1] + 2) % 8] != arr[i][(top[i] + 6) % 8] :
            tlst.append((i, (i - idx) % 2))
        else:
            break
    #left side of idx wheel
    for i in range(idx-1, 0, -1):
        if arr[i][(top[i] + 2) % 8] != arr[i + 1][(top[i+1] + 6) % 8] :
            tlst.append((i, (idx - i)%2 ))
        else:
            break
    
    for i, rot in tlst:
        if rot == 0:    #rotate same direction ( abs(idx - i) % 2 == 0 )
            top[i] = (top[i] - dr + 8) % 8
        else:
            top[i] = (top[i] + dr + 8) % 8
    
answer = 0
calc = [0, 1, 2, 4, 8]

for i in range(1, N+1):
    answer += arr[i][top[i]] * calc[i]

print(answer)

+α

• 참고
  • https://www.youtube.com/watch?v=0VfhMu6s21w&t=1s