[Algorithm] 백준 1009번 분산 처리 (Python)

https://www.acmicpc.net/problem/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

5
1 6
3 7
6 2
7 100
9 635

예제 출력 1

1
7
6
1
9

풀이

설명

• 제곱의 수가 커질수록 생각보다 훨씬 큰 수가 나와 시간 초과가 나올 수밖에 없다.
• 이를 해결하기 위해 1부터 10까지의 수의 제곱 수를 구해보면서 규칙을 알아냈다.
• 제곱 수를 10으로 나눈 나머지에 대한 규칙이다.

밑수	나머지
1	1
2	2 4 6 8
3	1 3 7 9
4	4 6
5	5
6	6
7	1 3 7 9
8	2 4 6 8
9	1 9
10	0

• 이를 토대로 문제를 해결하면 된다.
• 밑수가 10인 경우, 10으로 나눈 나머지가 0이 나온다.
  • 따라서 나머지가 0인 경우, 10을 출력한다.
• 밑수가 1, 5, 6인 경우, 10으로 나눈 나머지가 자기 자신이 나온다.
  • 따라서 나머지가 자기 자신인 경우, 자기 자신을 출력한다.
• 밑수가 4, 9인 경우, 10으로 나눈 나머지가 자기 자신과 밑수를 2번 곱한 수에 10을 나눈 수가 된다.
  • 밑수 : 4
    • 4^1 = 4, 4^2 = 16, 4^3 = 64, 4^4 = 256...
    • 지수가 홀수인 경우, 자기 자신
    • 지수가 짝수인 경우, 밑수^밑수 % 10
  • 밑수 : 9
    • 9^1 = 9, 9^2 = 81, 9^3 = 729, 9^4 = 6561...
    • 지수가 홀수인 경우, 자기 자신
    • 지수가 짝수인 경우, 밑수^밑수 % 10
• 밑수가 2, 3, 7, 8인 경우, 10으로 나눈 나머지가 4개씩 반복된다.
  • 따라서 지수를 4로 나눈 수가 짝수인지 홀수인지 나누어 해결한다. 
    • 지수%4가 홀수인 경우
      • 밑수를 지수만큼 제곱한 수에서 10을 나눈다.
    • 지수%4가 짝수인 경우
      • 밑수를 4만큼 제곱한 수에서 10을 나눈다.

코드

• 실패
  • 시간 초과 및 런타임 에러(TypeError)

import sys

input = sys.stdin.readline

T = int(input())

for i in range(T) :
    a, b = map(int, input().split())

    num = a**b

    if num <= 10 :
        print(num)
    else :
        num = num % 10
        if num == 0 :
            print(1)
        else :
            print(num)

• 성공

import sys

input = sys.stdin.readline

T = int(input())

for i in range(T) :
    a, b = map(int, input().split())

    a = a % 10 # 맨 뒷자리 수로 비교하므로 10으로 나눴을 때의 나머지 값과 같음

    if a == 0 : # 10의 배수
        print(10)
    elif a == 1 or a == 5 or a == 6 :
        print(a)
    elif a == 4 or a == 9 :
        b = b % 2 # 짝수인지 홀수인지 판단
        if b == 1 : # 홀수
            print(a)
        else : # 짝수
            print((a*a)%10)
    else : # 반복되는 수가 4개인 경우(2, 3, 7, 8)
        b = b % 4
        if b == 0 :
            print((a**4) % 10)
        else :
            print((a**b) % 10)