[BOJ] Python 백준 1009번 분산처리 브론즈 3

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

1009번: 분산처리

문제 풀이

---

브론즈 문제 치고 정답 비율이 24%로 엄청 낮은 통계였다.

 

왜 그런가 싶어서 문제를 자세히 봤더니 아마 생각난 방식 그대로 제출한다면 시간 초과가 날 것 같단 생각이 들었다.

 

문제 자체는 단순하게 데이터의 개수만큼 컴퓨터 대수인 10개를 나눈 나머지를 출력하고 0만 10으로 변환하면 되는데 여기서 문제는 데이터의 개수가 a^b 만큼 들어오고 a는 100 미만, b는 1000000 미만의 자연수이므로 총 100000000(1억) 개의 데이터가 될 수 있으며 심지어 테스트 케이스도 입력받기 때문에 단순하게 제곱수를 통한 구현은 시간 초과가 날 가능성이 높았기 때문이다.

 

혹시나 해서 그대로 구현하여 제출했더니 역시 시간 초과가 났다.

 

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

 

결과 화면

 

따라서 시간을 줄일 수 있는 방식을 생각해야 했고 일의 자리가 나올 수 있는 숫자들을 구해서 해당 개수만큼 나눈다면 어느 정도 정답에 근접할 것이라 생각했다.

 

다음은 통과한 전체 코드이다.

 

n=int(input())
for i in range(n):
    a,b=map(int,input().split())
    if a==1:
        print(1)
    else:
        last=a%10
        last_num=[last]
        sum_last=(last**2)%10
        while sum_last not in last_num:
            last_num.append(sum_last)
            sum_last=(sum_last*last)%10
        if last_num[(b-1)%len(last_num)]==0:
            print(10)
        else:
            print(last_num[(b-1)%len(last_num)])

 

먼저 4번째 줄에서 if문을 쓴 이유는 a가 1이라면 b가 어떤 숫자가 나와도 데이터 개수는 1개이므로 무조건 1이 나올 수밖에 없기 때문에 처리했다.

 

a가 1이 아닌 나머지의 경우엔 일의 자리를 구해서 리스트에 저장하고 동일한 숫자가 나오기 전까지 a를 곱하여 일의 자리를 계속해서 추가한다.

 

10으로 나누기 때문에 최대 10개가 나올 수 있으며 0은 10으로 치환해야 한다는 것을 잊으면 안 된다.

 

해당 반복문이 종료되면 인덱스는 0부터 시작하기 때문에 b-1을 last_num의 길이(일의 자리에 나올 수 있는 숫자들)로 나누고 해당 숫자가 0이면 10으로 치환, 아니면 해당 숫자를 출력하면 통과한다.

 

결과 화면

 

역시 구현 자체가 어려운 문제는 아니라 단순하게 생각해서 제출한 경우가 많아 정답 비율이 낮게 나온 것 같다.