[Python] BOJ 18291 - 비요뜨의 징검다리 건너기
www.acmicpc.net/problem/18291 18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net 일단 N=1일 때부터 직접 계산해보면서 규칙을 찾아보았다. N=1일 때 1, N=2일 때 1, N=3일 때 2, N=4일 때 4, N=5일 때 8 ... N=1일 경우를 제외하고 2의 (N-2)제곱이 나오는 것을 확인 할 수 있었다. 단순히 print(2**(N-2))를 하면 N의 범위가 최대 10**9이므로 O(10**9)가 되어서 시간초과가 발생한다. 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다. # 분할정복을 이용한 거듭제곱은 따로 정리해..
