N개의 계단으로 이루어진 계단이 있다고 가정해 보겠습니다. 한 번에 한 계단씩 천천히 오를 수도 있고, 각 차례마다 최대 N계단까지 한 번에 뛰어넘을 수도 있습니다. 이때 구해야 하는 것은 꼭대기 층까지 도달할 수 있는 방법의 총 개수입니다. 문제는 N 값이 매우 커질 수 있다는 점인데, 그래서 우리는 방법의 수 전체가 아니라 첫 K자리와 마지막 K자리에만 관심을 둡니다.
문제 이해하기
입력이 N = 10, k = 2라고 해보겠습니다. 이때 출력은 63입니다. 계단이 10개일 때 꼭대기까지 올라가는 방법의 수를 S라고 하면, S를 네 자리 숫자 wxyz 형태로 표현할 수 있습니다. 여기서 앞의 두 자리 wx와 뒤의 두 자리 yz를 더하면 63이 됩니다.
실제로 N개의 계단을 오르는 방법의 수는 2N-1입니다. N = 10이면 29 = 512가 되고, 앞 두 자리 51과 뒤 두 자리 12를 더하면 정확히 63이 나옵니다. 이렇게 되는 이유는 계단과 계단 사이의 경계(N-1개)마다 '여기서 멈출지, 뛰어넘을지' 두 가지 선택이 가능하기 때문입니다.
접근 방법
핵심 아이디어는 다음과 같습니다. 방법의 수가 2N-1이라는 것을 알고 있으므로, 결국 이 문제는 거듭제곱 계산으로 귀결됩니다. 하지만 N이 크면 2N 자체가 감당하기 어려울 만큼 거대한 숫자가 됩니다. 그래서 빠른 거듭제곱(제곱을 반복하는 방식)을 사용하되, 중간 결과마다 앞쪽 c자리만 잘라내어 숫자의 크기를 통제합니다. 마지막 k자리는 모듈러 연산으로 구하고, 앞 k자리는 잘라낸 값에서 다시 추출한 뒤 두 값을 더하면 답이 됩니다.
구체적인 단계는 다음과 같습니다 −
- N := N - 1
- c := 2 × ceil(k + log10(N)) — 중간 계산에서 유지할 자릿수
- e := N, b := 2, s := 1로 초기화
- e > 0인 동안 다음을 반복합니다:
- e가 홀수이면 s := s×b의 결과에서 앞 c자리만 남긴 값 (p는 s×b의 전체 자릿수)
- e := ⌊e / 2⌋
- b := b×b의 결과에서 앞 c자리만 남긴 값
- s := s에서 앞 k자리만 남긴 값
- r := s + (2N mod 10k)
- r을 반환합니다
예제
아래 구현을 통해 더 잘 이해해 보겠습니다 −
from math import log10,ceil
def solve(N,k):
N -= 1
c = 2*ceil(k + log10(N))
e = N
b = 2
s = 1
while e > 0:
if e % 2 == 1:
s = int(str(s*b)[:c])
e //=2
b = int(str(b*b)[:c])
s = str(s)[:k]
r = int(s) + pow(2, N, 10**k)
return r
N = 10
k = 2
print(solve(N,k))
입력
10, 2
출력
63
이 알고리즘은 반복 횟수가 O(log N) 수준이므로 N이 수억 단위로 커져도 전체 숫자를 다루지 않고 앞·뒤 자릿수만 유지하면서 매우 효율적으로 답을 계산할 수 있습니다.