[백준] 1009번 설탕 배달

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

 

 

 

풀이

이 문제를 파이썬으로 풀 때는 직접 a**b 를 구한 다음 % 10을 해서 푸는 간단한 방법도 있지만

파이썬 함수인 pow(A, B, 10) 을 하게되면 바로 (a^b)%10의 결과물을 얻을 수 있게 된다.
%의 결과가 0인 경우만 10번 컴퓨터가 수행하는 것으로 출력을 변경해주면 간단하게 풀 수 있다.

n = int(input())

for i in range(n):
    a, b = map(int, input().split())
    temp = pow(a,b,10)
    

    if temp == 0:
        print(10)
    else:
        print(temp)

하지만 이 방법이 아닌 다른 방법으로 푸는 것이 이 문제를 풀면서 얻을 수 있는 부분이라고 생각했다.

 

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다.

위 내용을 봤을 때 a^b 가 어떤 숫자인지는 중요하지 않고 %10을 했을 때 어떤 숫자가 나오는 지가 중요하다.

예시로 9*9를 들었을 때 81에서 1만 중요한 것이다. 그 이후 81*9를 한다고해도 729중 마지막 9만 의미있는 숫자이기 때문에 각 항목을 곱한 결과에 %10을 취해서 1의 자리 숫자만 남겨도 동일한 정답을 구할 수 있다.

 

n = int(input())

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

    if temp == 0:
        print(10)
    else:
        print(temp)

위 방식을 그대로 코드에 구현해봤다.
처음 temp는 1로 n의 0승을 나타내고 입력받은 b 제곱만큼 곱하는 동안 %10을 취하면서 계속 1의 자리 숫자로 변경해줬다.

python으로  제출을 하면 시간 초과가 나오고 pypy3로 제출했을 때는 정답이 나왔다.

 

# b 제곱을 구한 다음 한번에 % 10을 하는 방법
n = int(input())

for i in range(n):
    a, b = map(int, input().split())
    temp = 1
    for j in range(b):
        temp *= a
    temp = temp%10
    if temp == 0:
        print(10)
    else:
        print(temp)

혹시 % 10을 매번 하는 연산이 곱셈에 큰 의미가 없을까싶어 코드를 수정하고 돌려봤다.

다행히? 시간 초과가 나와서 % 10을 각 곱셈에서 수행하는 것이 좀 더 적은 시간이 소모된다는 것을 알 수 있었다.

물론 실제로 위 같은 문제가 나오면 pow 함수를 사용해서 가장 빠르게 구하는 것이 좋을 것 같다.

 

추가적으로 같은 수의 제곱은 규칙을 갖기 때문에 해당 성질을 이용해서도 문제를 풀 수 있다.

1 : 1 1 1 1 ...
2 : 2 4 8 6 2 4 8 6 ...
3 : 3 9 7 1 3 9 7 1 ...
4 : 4 6 4 6 4 ...
5 : 5 5 5 5 ...
6 : 6 6 6 6 ...
7 : 7 9 3 1 7 9 3 1 ...
8 : 8 4 2 6 8 4 ...
9 : 9 1 9 1 9 1 ...

위 리스트를 생성한 뒤 입력 받은 a 에 대하여 b를 모듈러한 값으로 한번에 구할 수 있다.