[Python] [백준] 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)

출력

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

예제

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

코드

t = int(input())

lst = [10,
       1,
       [2,4,8,6],
       [3,9,7,1],
       [4,6,4,6],
       5,
       6,
       [7,9,3,1],
       [8,4,2,6],
       [9,1,9,1]]

for _ in range(t):
    a, b = map(int, input().split())
    a = a % 10
    b = b % 4

    if a in [0, 1, 5, 6]:
        print(lst[a])
    else:
        print(lst[a][b-1])

 

설명

a와 b가 주어지면 a을 b로 제곱한 후, 일의 자리 수를 반환하면 된다. 예를 들어, a=6, b=2이면 6의 2 제곱은 36이므로, 일의 자리인 6을 반환한다. 직관적으로 짜면 아래와 같다.

t = int(input())
for _ in range(t):
    a, n = map(int, input().split())
    print(int(str(a**n)[-1]))

하지만 위 코드는 시간 초과에 걸리므로, 좀 더 간단한 규칙을 찾아 적용해야 한다. 예를 들어, 1은 어떤 자연수로 제곱하던지 간에 항상 1이며, 5는 어떤 자연수로 제곱하더라도 일의 자리는 항상 5이다. 이런 성질을 정리하면 다음과 같다.

 

$a^b$의 일의 자리수	b = 1	b = 2	b = 3	b = 4	b = 5	b = 6	b = 7	b = 8	반복 규칙
a = 1	1	1	1	1	1	1	1	1	1
a = 2	2	4	8	6	2	4	8	6	2 4 8 6
a = 3	3	9	7	1	3	9	7	1	3 9 7 1
a = 4	4	6	4	6	4	6	4	6	4 6
a = 5	5	5	5	5	5	5	5	5	5
a = 6	6	6	6	6	6	6	6	6	6
a = 7	7	9	3	1	7	9	3	1	7 9 3 1
a = 8	8	4	2	6	8	4	2	6	8 4 2 6
a = 9	9	1	9	1	9	1	9	1	9 1

반복되는 규칙을 이중 리스트로 만들어두고, 입력값에 맞게 출력해줬다.