[🥉3 / 백준 1009 / 파이썬] 분산처리

 

1009번: 분산처리

 

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

 

예제 입력  5 1 6 3 7 6 2 7 100 9 635

예제 출력  1 7 6 1 9

 

풀이

 

a^b의 수를 1~10 까지 번갈아가며 할당했을 때 마지막 순서를 찾는 문제이다.

 

단순히 a**b % 10을 출력하면 될 것 같지만, b의 범위가 최대 1,000,000이기 때문에 시간초과에 걸린다.

 

따라서 패턴이 있나 찾아보도록 하자.

 

a,b = map(int(input()))
num=1
arr = []
for i in range(b):
    num = num * a % 10
    if num not in arr:
        arr.append(num)
    else:
        break
print(arr)

 

위 코드를 실행하면 a,b 에 따라 일정한 패턴을 찾아준다.

 

a^b % 10을 수행하면 계속해서 같은 패턴의 숫자가 등장하기 때문에 b를 패턴의 길이로 나누어주면 된다.

 

그리고 b를 패턴의 길이로 나눠 준 나머지를 패턴의 인덱스에 넣으면 마지막에 등장할 숫자가 나온다.

 

단, 수가 0으로 끝나는 경우 10번째 컴퓨터에 할당한 것이므로 따로 처리를 해주자.

 

import sys
input = sys.stdin.readline
for i in range(int(input())):
    a, b = map(int,input().split())
    num=1
    arr = []
    # 패턴 찾기
    for i in range(b):
        num = num * a % 10
        if num not in arr:
            arr.append(num)
        else:
            break
            # 같은 숫자가 또 등장하면 패턴 찾기를 종료
    
    result = 0
    if (b%len(arr))-1 >= 0:
        result = arr[(b%len(arr))-1]
    else:
        result = arr[len(arr)-1]
    # b를 패턴의 길이로 나눈 나머지를 찾아준다.
    # 허나, 나머지에서 하나를 빼야 하는데 나머지가 0일 경우
    # -1이 되므로 배열의 끝 인덱스로 대체해준다.
        
    print(result if result != 0 else 10)
    # 값이 0일 경우 10으로 대체, 이외엔 제대로 출력