백준 1009번- '분산처리' (PYTHON 풀이)

문제:

처음에 이 문제를 보고 1~10번은 동일한 컴퓨터에 배정, 11번째는 다시 1번... 15번째는 5번 배정 이런식으로 배정하는 문제인데 왜 a^b 형태가 필요한거지? 라는 의문과 규칙이 뭘까를 많이 고민했던 것 같다.

일단 앞서 말한 것처럼 일반적으로 배정하는 방식이 아니라 a^b 형태로 배정하라고 하면서 한번 꼬아서 낸 문제인 것 같고, 규칙은 예제 출력을 통해서 알아냈다.

마지막 출력은 길어서 이미지 첨부는 생략하겠다.

예제 입력을 그대로 따라서 해보면, 모두 마지막 숫자가 출력되는 것을 알 수 있다.

그래서 일단은 무작정 문제를 풀기 위해서 일의 자리를 출력하면 된다고 생각해서 코드를 작성했다.

 

풀이:

N = int(input())

for i in range(N):
    a, b = map(int,input().split())
    li = list(str(a**b))
    print(li[-1])

이렇게 푸니까 당연히 시간초과가 났다.

적은 수의 제곱이면 몰라도 큰 수 일 경우 연산+리스트 저장+그 후 마지막 값 출력의 작업이 반복될테니 안될 거라고 얼추 예상은 했다.

그래서 다른 방법으로 풀기 위해 고민했다.

우리가 필요한 건 일의 자리이다. 즉, 일의 자리만 구하면 되는데 많은 연산을 해서 자릿수 전부를 계산할 필요가 없다는 얘기이다. 그래서 일의 자리만 출력하기 위해 새로운 규칙을 다시 찾아야 한다.

 

2의 거듭제곱을 예로 들어서 한번 규칙을 살펴보겠다.

2^1 = 2    → 2
2^2 = 4    → 4
2^3 = 8    → 8
2^4 = 16   → 6
2^5 = 32   → 2
2^6 = 64   → 4
2^7 = 128  → 8
2^8 = 256  → 6

2,4,6,8이 반복되는 것을 확인할 수 있다.

3^1 = 3 → 3
3^2 = 9 → 9
3^3 = 27 → 7
3^4 = 81 → 1
3^5 = 243 → 3
3^6 = 729 → 9
3^7 = 2187 → 7
3^8 = 6561 → 1

3의 거듭제곱은 3,9,7,1이 반복된다. 이처럼 특정 수의 거듭제곱을 보면 보통 1~4개씩 일의 자리수가 반복되는 것을 확인할 수 있다.

그러므로 우리는 이번 문제를 풀기 위해서 이러한 규칙을 활용하여 일의 자리수를 구하면 된다.

pattern = {
    0: [10],
    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]
}

모든 수의 규칙을 찾아서 딕셔너리 형태로 대입하면 코드를 작성하기 편하기 때문에 이를 미리 만들었다.

 

최종 코드:

import sys
input = sys.stdin.readline

pattern = {
    0: [10],
    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]
}

N = int(input())

for i in range(N):
    a, b = map(int,input().split())
    last = a % 10
    li = pattern[last]
    x = (b - 1) % len(li)
    print(li[x])

결과적으로 이렇게 작성하면 문제를 풀 수 있다.

앞서 말한대로 딕셔너리를 작성하고, 반복문을 돌면서 어떤 수를 기준으로 거듭제곱을 계산할지 구하기 위해 10 으로 나눈 나머지를 구한다. (이 값이 일의 자리이므로) 그 값을 last라는 변수에 넣고 이에 해당하는 딕셔너리 값을 li에 넣으면 a에 해당하는 키의 값들이 전부 들어가게 된다.

그 후 인덱스는 0부터 시작하지만 거듭제곱은 1부터 시작되기 때문에 -1을 해주고 전체 li의 길이로 나눠준 나머지에 해당하는 인덱스의 값이 우리가 원하는 답이 된다!