[python] Baekjoon 1009 : 분산처리

 

문제 - Baekjoon 1009 : 분산처리

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

1009번: 분산처리

핵심

분산처리에서 특정 작업이 처리될 컴퓨터의 번호 예측.

-> 두 정수의 나눗셈 결과를 출력하는 프로그램 작성.

내용

주어진 작업에 대해 마지막 숫자가 처리될 컴퓨터 번호를 예측하는 문제입니다. 각 작업은 a^b 형태로 주어지며, 이를 통해 마지막 데이터가 처리될 컴퓨터 번호를 찾아야 합니다.

 

프로그래밍 - (DALLE)

접근 방법

- a^b의 계산 결과 대신, a의 거듭제곱 패턴을 분석하여 마지막 숫자의 반복 패턴을 찾습니다.
- 각 숫자마다 반복되는 마지막 숫자의 패턴을 이용하여 b에 해당하는 마지막 숫자를 결정합니다.
- 패턴을 이용하는 방식으로 계산량을 줄이고 빠른 예측이 가능합니다.

코드

T = int(input())  # 테스트 케이스의 수

for _ in range(T):
    a, b = map(int, input().split())
    a %= 10  # a의 마지막 자리 숫자만 사용

    if a == 0:  # 0일 경우 항상 10번 컴퓨터
        print(10)
    else:
        cycle = [a]
        while True:
            next_num = (cycle[-1] * a) % 10
            if next_num == cycle[0]:  # 순환 패턴 시작
                break
            cycle.append(next_num)

        print(cycle[(b % len(cycle)) - 1])

풀이

- `a`의 마지막 자리 숫자만 사용하여 패턴을 찾습니다.
- `a`를 곱한 결과의 마지막 자리 숫자가 처음과 같아질 때까지 반복하여 패턴을 만듭니다.
- `b`를 패턴 길이로 나눈 나머지를 사용하여 해당되는 숫자를 출력합니다.

 

python coding

참고 자료

- Python의 나머지 연산자와 거듭제곱 연산에 대한 설명: [Python Official Documentation](https://docs.python.org/3/reference/expressions.html))
- 컴퓨터의 분산 처리에 관한 기본 이론: [Distributed Computing Wikipedia](https://en.wikipedia.org/wiki/Distributed_computing))