백준 15717번: 떡파이어

www.acmicpc.net/problem/15717

15717번: 떡파이어

---

본문을 읽어보면 바로 직전 글과 비슷한 부분이 있다고 느끼실 수 있을 것 같습니다.

(백준 18291번: 비요뜨의 징검다리 건너기)

 

실제로 $N$ 세를 먹는 방법을 $X_{N}$이라고 했을 때, $X_{N}$과 $X_{N+1}$의 관계식이 정확히 똑같이 나오게 됩니다.

 

그런데 $N=1$일 때의 경우의 수가 $X_{1}=1$ 인데

 

$N=2$일 때의 경우의 수가 $X_{2}=2$

 

이므로, 비요뜨의 징검다리 문제와는 다른 식이 나오게 됩니다.

 

즉,

 $X_{N}=2^{N-1}$

입니다.

 

또한 $N=0$인 경우가 입력으로 주어지므로 $X_{0}=1$도 고려해서 코드를 짜야합니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>
#define mod 1000000007

long long power_modular (long long base, long long power);

int main() {
	long long N;
	scanf("%lld", &N);
	if (N <= 1) {
		printf("1");
		return 0;
	}
	printf("%lld", power_modular(2, N - 1));
	return 0;
}

long long power_modular (long long base, long long power) {
	long long answer = 1;
	while(power) {
		if (power % 2) {
			answer = (answer * base) % mod;
		}
		base = (base * base) % mod;
		power /= 2;
	}
	return answer;
}

 

(C11, 1116KB, 0ms, 제출번호 26422402)

---

비요뜨의 징검다리 문제보다 조합론으로 푸는 난이도가 조금 더 올라갔습니다.

 

먼저 $X_{N}$ 을 다음과 같이 작은 문제들의 합으로 생각할 수 있습니다.

 

$N$세를 $1$일에 걸쳐 먹는 경우의 수 (둘째날 $0$개)

$N$세를 $2$일에 걸쳐 먹는 경우의 수 (셋째날 $0$개)

$N$세를 $3$일에 걸쳐 먹는 경우의 수 (넷째날 $0$개)

$\cdots$

$N$세를 $N$일에 걸쳐 먹는 경우의 수 ($N+1$째날 $0$개)

 

이때 $N$세를 $M$일에 걸쳐 먹는 경우의 수를 풀어보겠습니다. ($N\geq M$)

 

각 일마다 먹은 떡국 그릇의 수를 $D_{1}$ , $D_{2}$ , $\cdots$ , $D_{M}$ 으로 나타냈을 때,

 

$D_{1}+D_{2}+\cdots +D_{M}=N$

 

이 성립합니다. 이때 떡국을 1일부터 $M$ 일까지 하루라도 먹지 않으면 생을 마감하므로

 

$N$세를 $M$일에 걸쳐 먹는 경우의 수를 구하는 문제는

 

위 방정식의 자연수 해 순서쌍 $\left (D_{1},D_{2},\cdots,D_{M} \right )$의 수를 구하는 문제로 환원됩니다.

 

이는 중복조합을 이용하여 구할 수 있는데, 결과적으로 $\large \binom{N-1}{M-1}$이 됩니다.

 

이제 $\large \binom{N-1}{M-1}$ 의 값을 $M=1$ 부터 $M=N$ 까지 더해주면, 최종적으로

 

$X_{N}=2^{N-1}$

 

이 유도된 것입니다.

---

 

점화식을 유도하는 다른 방법으로는 비요뜨의 징검다리  문제에서 보여드렸던 직관적인 관찰도 나름대로 유용합니다.