[python/알고리즘] Softeer(소프티어) 바이러스 풀이

 

다음 문제의 조건은 아래와 같다.

 

 

해당 문제는 단순히 반복문으로 나눠서 풀게 되면 시간초과가 걸린다. 그래서 처음에 해당 방법으로 풀고 답은 맞는데 오류나서 애먹었는데 다른 분의 풀이를 보고 잘못된 점으로 알았다.

 

해당 문제를 푸는 방법은 여러가지가 있는데 1번째는 분할 정복이라는 방법이고 2번째는 파이썬 함수인 pow를 사용하는 것이다. 여기서는 pow를 이용하여 풀었다. 1번째 방법보다 훨씬 간단하다.

 

pow(base, exp, mod)으로 base를 exp 제곱하는 함수이고 mod 값을 넣으면 거듭제곱을 하면서 나머지 연산을 수행해주는 역할을 해주기 때문에 적어주는 것이 좋습니다.

 

제출한 코드 :

 

import sys
input = sys.stdin.readline

K, P, N = map(int, input().split())
print(K * pow(P,N,1000000007)%1000000007)

 

그 결과 :

 

 

풀면서 느낀 바이지만 소프티어는 시간복잡도, 메모리복잡도를 중요히 따지기 때문에 그런 부분을 꼼꼼히 따져서 오류가 안 나도록 조심하는 것이 좋다.