백준 / 1009번 / 분산처리 / Python / 시간복잡도

📚문제

출처 : 백준 1009번 (https://www.acmicpc.net/problem/1009)

📝풀이

# 1009번 분산처리
t=int(input())
for _ in range(t):
    a,b=map(int,input().split())   
    print((a**b)%10)

처음에 이렇게 풀어줬을 때는 

시간초과에 걸려버려서 오답...

b가 10,000까지 있어서 파이썬에서도 꽤 큰 수를 연산해야해서 1초는 넘게 된다

 

 

# 1009번 분산처리
t = int(input())
answer =[]

for _ in range(t):
    a,b = map(int,input().split())
    b %= 4
    
    if b%4==0:
        b=4
    
    s = a**b
    
    if s%10 ==0:
        answer.append(10)
    else:
        answer.append(s%10)

for i in answer:
    print(i)

 

출처 : https://blex.me/@laetipark/%EB%B0%B1%EC%A4%80bojpython-1009%EB%B2%88-%EB%B6%84%EC%82%B0%EC%B2%98%EB%A6%AC

다음은 a의 b승에 대해 정리한 표이다

이 표를 보고 문제를 이해하고 패턴을 파악할 수 있었다

0번 컴퓨터는 10번 컴퓨터로 생각하면된다

(a**b%10이 0이라면 10번컴퓨터인 10을 출력)

 

문제에서 a는 100까지 있고 b는 10,000까지 나오게 된다

근데 패턴을 보면 b가 4인이후로부터는 일의 자리수가 같게 나오게 된다

 

다른 풀이들에서는 a를 10으로 나눈 다음에 

a의 끝자리수가 1,5,6인경우 / 4,9 인경우/ ...

등을 고려하여 풀었는데

b의 패턴만 줄여주어도 시간은 충분했다

 

풀이 💡

b가 숫자 4까지를 기준으로 똑같은 패턴이 반복된다는 것을 파악했으므로

지수b를 4로 나눈 나머지를 구한다

(ex 1,2,3,0,1,2,3,0,...)

근데 이때 만약 b가 4의 배수라면은 나머지가 0이 되어버리기 때문에

계속 a의 0승을 구하게 된다 

 

그래서

b%4가 0이 된다면(=b가 4의 배수라면)

b를 0이 아닌 4로 변경해주어야 한다

 

 

 

 

+ 다른 풀이 💡

# 1009번 분산처리 - 풀이 2
t = int(input())

for _ in range(t):
    a,b = map(int,input().split())
    a %= 10 # 컴퓨터가 10대 있으므로 10을 주기로 같은 컴퓨터에 할당
            # ex) 11번째 데이터-> 1번 컴퓨터 , 12번째 데이터 -> 2번 컴퓨터
    
    # 0번컴퓨터 = 10번 컴퓨터
    # a가 10의 배수라면 위에서 10으로 나누는 과정에서 0이 나옴
    # 이때 값은 10(10번컴퓨터) 출력
    if a ==0:
        print(10)
        
    # a의 끝자리가 1,5,6인 경우 - 패턴 1
    elif a in [1,5,6]:
        print(a)
        
    # a의 끝자리가 4,9인 경우 - 패턴 2
    elif a in [4,9]: 
        if b%2==0: #a의 끝자리가 4나 9인 경우엔 b의 짝수/홀수 여부에 따라 값이 바뀜
            print(a**2%10) # 4일경우 : 4,6,4,6... / 9일경우 : 9,1,9,1...주기로 순환
                           # a의1승과 a의 2승만 보면 되기 때문에 b가 짝수일 경우 제곱한 뒤에 10으로 나누기
                           # %10은 1의 자리 수를 구하기 위함
        else:
            print(a)
    
    # a의 끝자리가 2,3,7,8인 경우 - 패턴 3
    else:
        b %= 4
        if b==0: # 위의 경우와 마찬가지로 4로 나누었을 때 0이 나오는 경우가 있을 수 있으므로
            print(a**4%10) # a의 0승이 아닌 4승으로 계산
        else:
            print(a**b%10)

제일 많은 풀이방법이다

처음에는 보고 이해가 잘 안되서 

직관적이고 쉬운 1번풀이를 작성했는데

찬찬히 보다보니 이해가 가서 

설명을 붙여서 다시 풀어보았다