BOJ 15717 - 떡파이어 (Python3)

이 문제보다 더 어렵고 구현하기도 빡센 돌아온 떡파이어라는 문제가 있다. 접근법은 영 다르지만 문제의 백스토리라거나 하는 것은 거의 같으니...

이 문제의 경우 18291번 문제와 아주 유사한 풀이방법을 가지고 있다. 어떻게 답이 얻어지는지만 알면 말이다.

 

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

---

문제

떡파이어의 불로장생의 비밀은 바로 떡국이다.

떡파이어는 떡국을 먹은 그릇의 개수만큼 나이를 먹는다. 그들은 매일 떡국을 먹는데, 떡국을 먹는대로 바로 소화가 가능하기 때문에 하루에 얼마든지 원하는만큼 떡국을 먹을 수 있다. 그러나 전에 떡국을 얼마나 먹었든지, 그들은 기구하게도 떡국을 하루라도 먹지 않으면 생을 마감하게 된다.

어느 날, 디디는 어떤 떡파이어가 N세로 생을 마감하기까지 어떤 생을 살아왔는지 알고 싶어서, 그의 나이를 먹는 과정의 경우의 수를 세려고 한다. 그렇지만, 떡파이어의 나이가 많을 수록 그 경우의 수는 무수히 많아지기 때문에 디디는 곤란해하고 있다.

그런 디디를 위해 N세로 생을 마감한 떡파이어가 나이를 먹는 과정의 경우의 수를 세는 프로그램을 작성해야 한다.

떡파이어의 나이는 0세부터 시작된다.

N이 3일때를 예로 들면,

첫째 날 3개, 둘째 날 0개

첫째 날 1개, 둘째 날 2개, 셋째 날 0개

첫째 날 2개, 둘째 날 1개, 셋째 날 0개

첫째 날 1개, 둘째 날 1개, 셋째 날 1개, 넷째 날 0개로

총 경우의 수는 4이다.

 

입력

정수 N이 주어진다. (0 ≤ N ≤ \(1012\))

 

예제 입력)

3

 

출력

나이를 먹는 방법의 가짓 수를 \(10^9+7\)로 나눈 나머지를 출력하시오.

 

예제 출력)

4

 

---

내 코드

a,b,c = 2,int(input())-1,1000000007
def power(a,b,c):
    if b<2: return (a**b)%c
    else:
        d = b//2
        return ((pow(a,d,c))**2)%c if b%2 == 0 else (a*(pow(a,d,c))**2)%c
print(power(a, b, c) if b!= -1 else 1)

 

우선 당연히 0세로 생을 마감한 떡파이어는 떡국을 한 그릇도 안 먹고 첫 날에 바로 임종하는 경우 하나가 존재한다는 것을 생각하자.

 

그 외의 경우에는, N세의 1과 N-1개의 +로 이루어진 1+1+1+1+...+1+1의 문자열을 생각을 해 보자.

여기서 날짜와 날짜를 구분하는 것을 공백으로 둘 것이다. 그러면 N살로 생을 마감한 떡파이어의 떡국 먹기 시퀀스는 저 문자열에서 적당한 +를 공백으로 치환한게 되는 것이다.

첫 날에 3개, 둘째 날에 2개, 셋째 날에 4개, 넷째 날에 0개를 먹고 9살로 생을 마감한 떡파이어는 1+1+1 1+1 1+1+1+1로 나타낼 수 있단 것이다.

총 N-1개의 + 중 임의의 +를 공백으로 바꾸는 가짓수는? \(2^{N-1}\)가지,

분할 정복을 통한 거듭제곱법으로 답을 출력하면 끝이다!

 

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

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