[Python] BOJ 18291 - 비요뜨의 징검다리 건너기

www.acmicpc.net/problem/18291

18291번: 비요뜨의 징검다리 건너기

 

일단 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)가 되어서 시간초과가 발생한다.

 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다.

# 분할정복을 이용한 거듭제곱은 따로 정리해서 포스팅해놓았다: hbj0209.tistory.com/43

[Algorithm] 분할정복을 이용한 거듭제곱

 

코드는 다음과 같다.

def pow(a,b):
	res = 1
	while b:
		if b & 1:
			res *= a
		a = a*a
		b >>= 1
	return res
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
	else:
		print(pow(2,N-2))

처음에 위와 같이 단순히 분할정복을 이용한 거듭제곱을 이용해 풀었는데도 시간초과가 떴다..

재귀로 해도 안되고 반복문으로 해도 안되서 헤매다가 10**9+7로 나누지 않고 있었다는 것을 깨달았다.

(문제 좀 제대로 읽자;;)

아래 코드와 같이 연산을 할 때마다 mod인 10**9+7로 나눠주면서 연산하니 통과가 되었다!

mod = 1000000007
def pow(a,b):
	res = 1
	while b:
		if b & 1:
			res *= a
			res %= mod
		a = a*a
		b >>= 1
		a %= mod
	return res
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
	else:
		print(pow(2,N-2))

 

(solved.ac 티어: 실버 1)

 

# 문제를 맞춘 뒤 고수들의 코드를 보니 Python은 그냥 내장함수 pow를 쓰면 통과가 된다. 배신감이 들었다...