[Python] 백준 1009번 : 분산처리

Problem

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

Solution

이 문제는 a^b를 10으로 나눴을 때의 나머지를 구하는 문제이다. 처음 문제를 보고나서 큰 고민 없이 아래의 코드를 제출했다가 2번 연속 시간초과로 오답처리가 되었다.

오답코드

import sys

t = int(sys.stdin.readline())
for i in range(t):
  a,b = map(int, sys.stdin.readline().split())
  n = pow(a,b)%10
  print(n)

이 코드엔 문제가 있는데 입력값의 조건이 (1 ≤ a < 100, 1 ≤ b < 1,000,000)인 상황에서 a, b 각각에 최댓값이 입력되면 처리시간이 오래 걸리게 된다. 따라서 처리과정의 효율화가 필요하다. 또한 나머지가 0이 나올때 0이 출력되는 문제도 있다.

정답코드

import sys

def first_digit(a,b):
  a %= 10
  if a==0:
    return 10
  elif a==1 or a==5 or a==6:
    return a
  elif a==4 or a==9:
    b %= 2
    return a**(b+2) % 10
  elif a==2 or a==3 or a==7 or a==8:
    b %= 4
    return a**(b+4) % 10
    

t = int(sys.stdin.readline())
for i in range(t):
  a,b = map(int, sys.stdin.readline().split())
  n = first_digit(a,b)
  print(n)

알아야 하는 결과는 1의 자리이기 때문에 a를 10으로 나눈 뒤 거듭제곱을 하여 1의 자리만 관찰하기로 했다. 그렇게 0~9까지 총 10개의 수가 생기는데, 1, 5, 6의 경우 거듭제곱해도 같은 수가 나온다. 4, 9의 경우 2개의 수가 반복되며 2, 3, 7, 8은 4개의 수가 반복된다. a의 나머지를 구했을 때 나누어 떨어지는 경우 n⁰=1이 나오는 경우를 막기 위해 나누는 수를 한번 더 더해주었다.

Memo

입력되는 값의 조건을 유심히 살필 필요가 있다.