BOJ 18291 - 비요뜨의 징검다리 건너기 (Python3)

오랜만에 골드 문제의 풀이와 함께 돌아왔다.

분할 정복이라는 새로운 개념을 배우고 나서 하루에만 열 개 가까이 골드 문제를 처리했다.

한 방법을 새로이 알게 되면 아무래도 그 방법을 이용해 풀 수 있는 문제는 전부 도전해 보는 편이라.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

비요뜨는 지금 강 앞에 서 있다. 강 위에는 징검다리가 놓여 있다.

징검다리는 비요뜨가 있는 방향에서부터 반대 방향까지 차례로 1번, 2번, ..., N번의 번호를 가지고 있다.

비요뜨는 1번 징검다리 위에 올라갔다. 그리고 아래 두 가지 규칙을 지키며 징검다리를 건너려고 한다.

• 1 ≤ X ≤ N 인 임의의 정수 X에 대해, 현재 있는 징검다리의 번호를 i번이라고 할 때 i+X번 징검다리로 뛸 수 있다.
• N번째 징검다리를 지나쳐선 안 되고, 정확히 도착해야 한다.

비요뜨는 자신의 특기인 코딩을 살리기 위해 노트북을 켰지만, 실수로 노트북을 강에 빠뜨리고 말았다.

비요뜨를 대신해 강을 건너는 경우의 수를 구해 주자!

 

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. (1 ≤ T ≤ 1000)

각 테스트 케이스는 한 줄로 구성되며, 징검다리의 개수를 의미하는 N이 주어진다. (1 ≤ N ≤ \(10^9\))

 

예제 입력)

1
4

 

출력

각 테스트 케이스에 대해, 한 줄에 하나씩 규칙을 만족하면서 징검다리를 건너는 경우의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.

 

예제 출력)

4

강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다.

---

내 코드

c = 1000000007
def power(b):
    if b<2: return (2**b)%c
    else:
        d = b//2
        return ((power(d))**2)%c if b%2 == 0 else (2*(power(d))**2)%c
for _ in range(int(input())):
    N = int(input())
    print(1 if N<3 else power(N-2))

 

우선 경우의 수부터 살펴보자.

징검다리를 건너려면 1번과 N번 돌은 꼭 밟아야 하니 N=1, 2일 때는 건너는 방법이 유일할 것이다. 다른 방법이 전혀 없으니까.

대신 N이 3 이상일 경우에는 2번, ..., N-1번 돌을 밟거나, 밟지 않는 식으로 건너야만 하므로 경우의 수가 정확히 \(2^{N-2}\)가지가 되어야 할 것이다.

각 2번, ..., N-1번의 N-2개의 돌에 대해서 각각 밟거나, 밟지 않는 두 가지 경우의 수가 있으니 말이다.

 

power(b)는 2의 b제곱을 c(\(10^9+7\))로 나눈 나머지를 뱉는 함수이다.

우선 b가 2보다 작을 경우 당연히 2의 b제곱을 뱉어도 된다. b가 사실 어느 정도 작으면 그냥 뱉어도 되고.

그러나 여기 문제에서는 N이 무려 10억까지 커진다. 이 정도 되면 연산을 하지 않더라도 메모리를 기가바이트 단위로 잡아먹게 된다.

그럴 때를 대비하여 만들어 놓은 것이 바로 power(b).

만약 b가 2x 꼴일 경우 power(x)*power(x)을 c로 나눈 나머지가 곧 power(b)를 c로 나눈 나머지와 같을 것이고, b가 2x+1꼴일 경우에는 2*power(x)*power(x)를 c로 나눈 나머지가 곧 power(b)를 c로 나눈 나머지와 같을 것이다.

남은 것은 power(N-2)를 N이 3 이상일 때, N이 3보다 작을 때는 1을 출력하게 하도록 프로그래밍하면 끝.

 

이로서 18291번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.