[Python] BOJ/백준 1009번 분산처리

[문제]

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

1009번: 분산처리

 

[풀이]

지수인 b가 백만까지 가능한 걸로 봐서 딱 봐도 간단하게 a ** b 를 이용해서 풀 문제는 아닐 것 같았다.

우선 예제에서 나온 숫자로 규칙성을 찾아보니 1의 자리에 같은 숫자가 반복되는 규칙성이 있었다.

 

처음에는 제곱한 수의 마지막 자리를 인덱싱해 가져와 그 수가 베이스 수와 같은지 확인을 했다.

예를 들어 베이스 수가 9일 경우, 제곱한 수 81의 1의 자리 숫자 1은 9과 같지 않아 패스, 세제곱 한 수 729의 1의 자리 숫자는 9와 같기 때문에 break 해 반복문을 나왔다. 그러나 이 방법은 일일이 비교를 해야만 해서 시간 초과가 떴다.

 

때문에 아예 알고리즘을 바꿔야 했는데, 다른 규칙을 찾아보니 모든 숫자가 전부 4개로 묶일 수 있었다.

따라서 b를 4로 나누어 나온 나머지를 제곱 해 나온 수의 1의 자리 수를 출력하면 되는 문제이다. 그러나 b를 4로 나눌 경우, 나머지가 0이 될 수 있어 나눈 후 4를 더해주었다.

 

[코드]

- 시간 초과

if __name__ == '__main__':
    t = int(input())
    tcase_li = []
    for i in range(t):
        a, b = map(int, input().split())
        tcase_li.append((a, b))

    for i in tcase_li:
        # 계산
        last_li = [str(i[0])]
        for j in range(2, i[1]):
            s = str(i[0] ** j)[-1:]
            if str(i[0]) == s:
                break
            else:
                last_li.append(str(i[0] ** j)[-1:])

        # 결과
        result = last_li[(i[1] % len(last_li))-1]
        print(result)

 

- 제출 코드

if __name__ == '__main__':
    t = int(input())
    results = []

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

        if a % 10 == 0:
            results.append(10)
        else:
            n = b % 4 + 4
            data = str(a ** n)[-1]
            results.append(data)

    for result in results:
        print(result)