[백준] 분산처리

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

1009번: 분산처리

 

< 문제 설명 >

컴퓨터가 10대가 있다. 

데이터의  개수는 항상 a^b개가 주어진다.

그리고 컴퓨터 하나와 데이터 하나 순서대로 짝지어진다.

이때, 마지막 데이터는 몇번째 컴퓨터에서 처리되는가?

 

 

< 문제 이해 >

단순하게 a^b를 구하고 10으로 나눈 나머지의 값을 출력하면 된다고 생각함.

 

 

< 시행 착오 >

m = int(input())

for i in range(m):
    a, b = (map(int, input().split()))
    print(a**b % 10)

처음에 이 코드를 이용해 풀었다가 시간 초과가 나왔다.

당연한 것이 for문이 999,999번 돌아가는 경우도 있기 때문!!!!!!

 

 

< 문제 풀이 >

어떤 숫자를 10으로 나눠서 나오는 나머지가 10개니까

0부터 9까지 나올 수 있는 나머지를 모두 고려해주는 방법을 사용했다.

즉, 1일 경우 1^1=1, 1^2=1이니까 1을 나눴을 땐 나머지가 1 하나이다.

2일 경우, 2^1=2, 2^2=4, 2^3=8, 2^4=16, 2^5=32 이기 때문에

나머지가 2, 4, 8, 6이 반복되는 것을 알 수 있다. 

이런 식으로 9까지  구해준다.

 

이때, 0의 경우에는 계속  0이니까 처음에  0으로 써줬다가 틀렸다.

나머지가 0이되는 경우에는 10번째 컴퓨터에 배정을 받기 때문에 0이 아니고 10이다.

 

m = int(input())
data = [[10],[1],[2,4,8,6],[3,9,7,1],[4,6],[5],[6],[7,9,3,1],[8,4,2,6],[9,1]]

for i in range(m):
    a, b = map(int, input().split())
    num = data[a % 10]
    print(num[b % len(num) - 1])

 

 

 

잘 풀어놓고 실패해서 봤더니 데이터 입력을 잘못했다^^;;