[백준] 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)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

---

풀이

 

처음 풀이는 단순히 a ** b를 통해 수를 직접 계산하고 str로 캐스팅 후 맨 뒷자리 [-1]를 뽑아내는 식으로 코드를 짰는데 시간초과가 발생하였다. 

 

문제에서 필요한 것은 일의 자리의 숫자이다. 숫자가 얼마가 되든 상관없이 일의 자리 숫자만 알아낼 수 있다면 문제를 해결할 수 있다는 의미이다.

 

반복되는 규칙을 찾자.

1의 거듭제곱

• 1, 1, 1, 1, 1, 1......
• 1이 반복

2의 거듭제곱(일의 자리만 나타냄)

• 2, 4, 8, 6, 2, 4, 8, 6......
• [2, 4, 8, 6]이 반복되는 패턴

3의 거듭제곱

• 3, 9, 7, 1, 3, 9, 7, 1......
• [3, 9, 7, 1]이 반복되는 패턴

4의 거듭제곱

• 4, 6, 4, 6, 4, 6......
• [4, 6]이 반복되는 패턴

5의 거듭제곱

• 5, 5, 5, 5, 5, 5....
• 5가 반복

6의 거듭제곱

• 6, 6, 6, 6, 6, 6, 6...
• 6이 반복

7의 거듭제곱

• 7, 9, 3, 1, 7, 9, 3, 1
• [7, 9, 3, 1]이 반복

8의 거듭제곱

• 8, 4, 2, 6, 8, 4, 2 ,6
• [8, 4, 2, 6]이 반복

9의 거듭제곱

• 1, 9, 1, 9, 1, 9.....
• [1, 9]이 반복

 

가장 긴 패턴의 길이가 4이기 때문에 모든 패턴의 길이를 4로 맞춘다면 패턴화가 가능해진다.

주어진 a값에 대한 패턴을 리스트로 만드는 코드이다.

result = [(a ** i) % 10 for i in range(1,5)]

 

여기서 b를 통해 원하는 결과의 일의 자리를 찾는 코드

result[(b % 4) -1]

 

0이 나오면 10번째 컴퓨터가 처리하도록하는 조건문을 추가하여 전체 코드를 작성하면

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    a, b = map(int, input().split())
    result = [(a ** i) % 10 for i in range(1,5)]
    print(result[(b % 4) -1] if result[(b % 4) -1] != 0 else 10)

 

위와 같이 나타낼 수 있다. 브론즈 문제라고 별 생각없이 풀다가 한 방 맞은 것 같은 기분이랄까?..