BOJ(백준) 14891[톱니바퀴]

안녕하세요, 이번 글에서는 백준 14891번 문제인 “톱니바퀴” 문제를 함께 해결해 보겠습니다. 이 문제는 주어진 회전 명령에 따라 톱니바퀴를 회전시키고, 최종 상태를 바탕으로 점수를 계산하는 문제입니다. 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/14891

1. 문제 설명

 

1) 문제 개요

네 개의 톱니바퀴가 있습니다. 각 톱니바퀴는 8개의 톱니를 가지고 있으며, 각 톱니는 N극 또는 S극을 나타냅니다. 주어진 회전 명령에 따라 톱니바퀴를 회전시키고 최종 상태를 바탕으로 점수를 계산하는 문제입니다.

 

2) 입력

• 첫 번째 줄부터 네 줄에 걸쳐 각 톱니바퀴의 상태가 주어집니다. 상태는 8개의 숫자로 이루어진 문자열로, 0은 N극, 1은 S극을 나타냅니다.

• 다섯 번째 줄에 회전 횟수 K가 주어집니다. (1 ≤ K ≤ 100)

• 이후 K개의 줄에 걸쳐 회전 명령이 주어집니다. 각 명령은 두 개의 정수로 이루어져 있으며, 첫 번째 정수는 회전시킬 톱니바퀴의 번호, 두 번째 정수는 회전 방향입니다. 1은 시계 방향, -1은 반시계 방향을 나타냅니다.

 

3) 출력

• 최종 톱니바퀴의 상태를 바탕으로 점수를 계산하여 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 톱니바퀴의 상태를 입력받아 배열에 저장합니다.

• 회전 명령을 입력받아 리스트에 저장합니다.

 

2) 회전 결정

• 회전 명령을 처리하면서 각 톱니바퀴의 회전 여부를 결정합니다.

• 현재 톱니바퀴의 회전에 따라 인접한 톱니바퀴가 회전할지 여부를 결정합니다.

• 맞물린 톱니가 다르면 반대 방향으로 회전합니다.

 

3) 회전 수행

• 각 회전 명령을 실제로 수행하여 톱니바퀴의 상태를 갱신합니다.

• 각 톱니바퀴의 12시 방향을 가리키는 톱니의 인덱스를 업데이트합니다.

 

4) 점수 계산

• 각 톱니바퀴의 12시 방향을 기준으로 점수를 계산하여 합산합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 톱니바퀴 상태를 저장할 배열 초기화, 처음에 빈 값을 하나 넣어 1번 인덱스부터 사용
arr = [[0] * 8]
for _ in range(4):
    arr.append(list(map(int, input().rstrip())))

# 각 톱니바퀴의 현재 톱니가 12시 방향을 가리키는 인덱스를 저장하는 배열 초기화
top = [0] * 5
K = int(input())  # 회전 횟수 입력 받음

for _ in range(K):
    move = []  # 회전 명령을 저장할 리스트
    idx, dr = map(int, input().split())  # 회전할 톱니바퀴 번호(idx)와 방향(dr) 입력 받음
    move.append((idx, dr))  # 처음 회전할 톱니바퀴와 방향을 리스트에 추가

    # 현재 톱니바퀴 기준 오른쪽 톱니바퀴 회전 여부 결정
    for i in range(idx+1, 5):
        if arr[i-1][(top[i-1] + 2) % 8] != arr[i][(top[i] + 6) % 8]:  # 맞닿는 톱니가 다르면
            if (i - idx) % 2 != 0:  # 홀수 번째 떨어진 톱니바퀴는 반대 방향 회전
                move.append((i, -dr))
            else:  # 짝수 번째 떨어진 톱니바퀴는 같은 방향 회전
                move.append((i, dr))
        else:
            break  # 맞닿는 톱니가 같으면 더 이상 회전하지 않음
    
    # 현재 톱니바퀴 기준 왼쪽 톱니바퀴 회전 여부 결정
    for i in range(idx-1, 0, -1):
        if arr[i+1][(top[i+1] + 6) % 8] != arr[i][(top[i] + 2) % 8]:  # 맞닿는 톱니가 다르면
            if (idx - i) % 2 != 0:  # 홀수 번째 떨어진 톱니바퀴는 반대 방향 회전
                move.append((i, -dr))
            else:  # 짝수 번째 떨어진 톱니바퀴는 같은 방향 회전
                move.append((i, dr))
        else:
            break  # 맞닿는 톱니가 같으면 더 이상 회전하지 않음
    
    # 회전 명령을 실제로 수행
    for idx, dr in move:
        top[idx] = (top[idx] - dr + 8) % 8  # 방향에 따라 톱니바퀴의 12시 방향 갱신

# 최종 점수 계산
ans = 0
for i in range(1, 5):
    if i == 1:
        ans += (arr[i][top[i]] * 1)
    elif i == 2:
        ans += (arr[i][top[i]] * 2)
    elif i == 3:
        ans += (arr[i][top[i]] * 4)
    elif i == 4:
        ans += (arr[i][top[i]] * 8)

print(ans)  # 최종 점수 출력

 

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 네 개의 톱니바퀴 상태를 입력받습니다.

• 다섯 번째 줄에서 회전 횟수 K를 입력받습니다.

• 이후 K개의 회전 명령을 입력받습니다.

 

2) 변수 초기화

• arr 배열: 각 톱니바퀴의 상태를 저장합니다.

• top 배열: 각 톱니바퀴의 12시 방향을 가리키는 인덱스를 저장합니다.

• move 리스트: 회전 명령을 저장합니다.

 

3) 회전 여부 결정

• 각 회전 명령에 대해 현재 톱니바퀴를 기준으로 오른쪽과 왼쪽 톱니바퀴의 회전 여부를 결정합니다.

• 맞물린 톱니가 다르면 반대 방향 또는 같은 방향으로 회전합니다.

 

4) 회전 수행

• 각 회전 명령을 실제로 수행하여 톱니바퀴의 상태를 갱신합니다.

• 각 톱니바퀴의 12시 방향 인덱스를 갱신합니다.

 

5) 점수 계산

• 각 톱니바퀴의 12시 방향을 기준으로 점수를 계산하여 최종 점수를 출력합니다.\

 

시간 복잡도 계산

이 문제의 시간 복잡도를 계산하기 위해 각 단계의 시간 복잡도를 고려해야 합니다.

1) 입력 처리

• 톱니바퀴 상태를 입력받는 부분: O(1)

• 회전 명령을 입력받는 부분: O(K), 여기서 K는 회전 명령의 수입니다.

2) 회전 여부 결정

• 각 회전 명령마다 오른쪽과 왼쪽 톱니바퀴를 확인하는 부분:

• 각 톱니바퀴마다 최대 4개의 톱니바퀴를 확인할 수 있으므로 이 부분은 O(1)입니다.

3) 회전 수행

• 각 톱니바퀴의 12시 방향 인덱스를 업데이트하는 부분: O(K), 여기서 K는 회전 명령의 수입니다.

4) 최종 점수 계산

• 각 톱니바퀴의 12시 방향을 기준으로 점수를 계산하는 부분: O(1)

 

따라서, 전체 시간 복잡도는 입력 처리와 회전 수행 단계에서 O(K)입니다. 즉, 이 문제의 시간 복잡도는 O(K)입니다.

5. Github으로 확인

coTest/BOJ/BOJ01_08_05_14891.py at main · pcy4196/coTest