[백준] 1009번 : 분산 처리 / 파이썬 / 구현

구현 / 수학 알고리즘에 해당하는 '1009: 분산처리' 문제이다.

---

딱 문제를 보자마자 아래와 같은 코드로 작성했는데 시간초과가 떴다.
나름 sys.stdin.readline()을 통해 방지했다고 생각했는데 다른 문제였다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    print((a ** b) % 10)

문제에서 a와 b의 최대 값 조건을 무시하고 풀어서 시간 초과가 뜬 것이었다.
a는 최대 100, b가 백만까지 될 수 있으므로 ab를 계산하는 과정에서 시간 복잡도가 증가한다.

---

💡 정답 코드

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    a, b = map(int, sys.stdin.readline().split())
    a = a % 10
    if (a == 1 or a == 5 or a == 6):
        print (a)
    elif (a == 0):
        print (10)
    elif (a == 2 or a == 3 or a == 7 or a == 8):
        b = b % 4 
        if (b == 0):
            print((a**4)%10)
        else:
            print((a ** b)%10)
    elif (a == 4 or a == 9):
        b = b % 2 
        if (b==0):
            print((a**2)%10)
        else:
            print((a ** b)%10)

---

📚 해결 과정

우선, 수가 너무 커지는 문제를 해결하기 위해서 10대의 컴퓨터가 데이터를 처리하기 때문에 몇 바퀴를 돌아도 일의 자리가 동일하다는 점을 사용하였다.

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

위와 같은 규칙이 반복되기 때문에 a의 값을 10으로 나눈 나머지 값으로 설정해주고 각 경우에 따라 나눠줬다.

반복되는 규칙에 따라 나눠준 후 그 안에 b의 값을 통해 한 번 더 나눠주면 시간 초과 문제를 해결할 수 있었다.

예를 들어 1, 5, 6은 a 값 그대로 값을 출력해주면 되고 4와 9는 두 개의 값이 반복되어 나오기 때문에 b를 2로 나눈 나머지로 계산해준 후 그 안에서 b가 0인 경우와 1인 경우로 나눠서 값을 계산해주면 된다.

---

• 단순히 알고리즘을 푸는 방법만 생각할게 아니라 시간 복잡도 및 문제에서 주어진 조건들을 꼼꼼히 살펴야함을 알 수 있었다.
• 숫자에서 나타나는 규칙도 빠르게 파악할 수 있도록 연습이 필요하다고 느꼈다.

+) 이외에도 다른 쉬운 문법에서 실수가 있어서 금방 풀지는 못했다 😭