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

[문제 출처]

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

1009번: 분산처리

 

[소스 코드1 - 시간 초과]

10대의 컴퓨터가 있고, a^b개의 데이터가 있다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터,... 11번 데이터는 1번 컴퓨터가 처리한다고 할 때

가장 마지막 데이터를 처리하는 컴퓨터 번호를 출력하는 문제이다.

 

문제에서도 알 수 있듯이 데이터의 개수의 일의 자릿수가 컴퓨터 번호를 결정한다.

즉 데이터 개수를 10으로 나눴을 때 나머지(0~9)와 동일한 번호가 컴퓨터 번호이다.

예외적으로 10으로 나누면 나머지가 0이므로 0일 때 10번 컴퓨터가 마지막 데이터를 처리한다.

 

하지만 이대로 코드를 작성하면 시간초과가 발생한다.

a와 b가 작을 때는 괜찮지만 커지면 a**b 연산 결과가 매우 커지기 때문이다. 따라서 다른 풀이 방법이 필요하다.

#1009

T = int(input())

for i in range(T):
  a,b = map(int, input().split())
  data = a**b
  
  result = data%10

  if result == 0:
    print(10)
  else:
    print(result)

 

[소스 코드2 - 맞았습니다!!]

 

a의 일의 자릿수가 뭐냐에 따라서 데이터 수의 일의 자리가 달라지기 때문에 미리 계산한다면 시간 초과를 막을 수 있다.

 

아래는 a의 일의 자릿수에 따른 계산 결과이다.

 

예를 들어 a=12라고 할 때

a%10 = 2

2^1 = 2  2^2 = 4  2^3 = 8  2^4 = 16  2^5 = 32  2^6 = 64

이런 식으로 2 4 8 6이 반복된다.

1 > 1
2 > 2 4 8 6
3 > 3 9 7 1 
4 > 4 6 
5 > 5
6 > 6
7 > 7 9 3 1
8 > 8 4 2 6
9 > 9 1 
0 > 0 : 10

#1009

T = int(input())

for i in range(T):
  a,b = map(int, input().split())
  num = a%10
  
  if num == 0:
    print(10)
  elif num in [1,5,6]:
    print(num)
  elif num in [4,9]:
    if b%2==0:
      print(num**2%10)
    else:
      print(num)
  else:
    if b%4==0:
      print(num**4%10)
    else:
      print(num**(b%4)%10)

num은 a를 10으로 나눴을 때 나머지이다.

num이 0이라면 10의 배수이므로 a를 몇 번 곱하더라도 데이터의 개수는 10의 배수가 되므로 10을 출력한다.

 

num이 1 5 6의 경우는 몇 번 곱하더라도 일의 자릿수는 num과 동일하므로 num을 출력한다.

 

num이 4 9인 경우는 2개의 수가 반복되므로, 홀수번 곱했을 때는 자기 자신을, 짝수번 곱했을 때는 제곱한 값을 10으로 나눈 값을 출력한다.

 

나머지 경우는 4가지가 반복되므로 4의 배수번 num을 곱해주었을 때와 나머지 경우에 대해서 나눠서 계산하여 출력한다.