문제 설명
어떤 사람이 가격이 x인 제품을 구매하려고 합니다. 그런데 하루가 지날 때마다 제품의 가격은 전날 가격의 x배 수준으로 빠르게 올라갑니다. 우리가 구해야 할 값은, 이 사람이 구매를 결심한 시점부터 y일 후의 제품 가격입니다. 가격이 지수적으로 증가하기 때문에 숫자가 감당하기 어려울 만큼 커질 수 있으므로, 답은 10⁹ + 7로 나눈 나머지(modulo)로 출력합니다.
입력은 쌍(pair)의 리스트 형태로 주어집니다. 각 쌍에서 첫 번째 값은 초기 가격 x, 두 번째 값은 경과한 일수 y를 의미합니다.
입출력 예시
예를 들어 입력이 다음과 같다고 해보겠습니다.
nums = [(5, 2), (6, 8), (2, 12),
(2722764242812953792238894584, 3486705296791319646759756475),
(1505449742164712795427942455727527, 61649494321438487460747056421546274264)]
이때 기대되는 출력은 다음과 같습니다.
25 1679616 4096 754504594 32955023
계산 과정을 살펴보면 다음과 같습니다.
- 5² = 25
- 6⁸ = 1679616
- 2¹² = 4096
- 2722764242812953792238894584의 3486705296791319646759756475제곱 = 754504594 (10⁹ + 7로 나눈 나머지)
풀이 접근 방법
이 문제의 핵심은 모듈러 거듭제곱(modular exponentiation)입니다. 다행히 파이썬의 내장 함수 pow()는 세 개의 인자를 받으면, 밑(base)의 지수(exponent) 승을 모듈러 값으로 나눈 나머지를 매우 효율적으로 계산해 줍니다. 내부적으로 분할 정복 방식을 사용하기 때문에 지수가 아무리 커도 O(log y) 시간 안에 처리됩니다.
알고리즘은 다음과 같습니다.
- 0부터 nums의 크기까지 반복합니다.
- 각 반복에서 x에는 nums[i][0]을, y에는 nums[i][1]을 대입합니다.
- pow(x, y, 10⁹ + 7)의 값을 출력합니다.
구현 코드
아래 예제를 통해 더 자세히 이해해 보겠습니다.
def solve(nums):
for i in range(len(nums)):
x, y = nums[i][0], nums[i][1]
print(pow(x, y, 1000000007))
solve([(5, 2), (6, 8), (2, 12),
(2722764242812953792238894584, 3486705296791319646759756475),
(1505449742164712795427942455727527, 61649494321438487460747056421546274264)])
입력
[(5, 2), (6, 8), (2, 12), (2722764242812953792238894584, 3486705296791319646759756475), (1505449742164712795427942455727527, 61649494321438487460747056421546274264)]
출력
25 1679616 4096 754504594 32955023
마무리
거듭제곱 값이 기하급수적으로 커지는 상황에서는 pow(x, y, m)처럼 모듈러 연산을 함께 수행하는 함수를 활용하면 성능 저하 없이 깔끔하게 답을 구할 수 있습니다. 파이썬은 임의 정밀도 정수를 기본 지원하지만, 지수가 천문학적인 규모일 때는 모듈러 거듭제곱이 사실상 필수적인 접근 방식입니다.