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

www.acmicpc.net/problem/18291

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

---

이런 문제는 규칙이 한 번에 보이지 않으면 N을 1에서부터 차근차근 키워보며 규칙을 찾는 방법이 좋다고 생각합니다.

 

$N=1$일 때, 경우의 수는 1가지 밖에 존재할 수 없습니다.

 

$N=2$일 때, 경우의 수는 마찬가지로 1가지 밖에 존재할 수 없습니다.

 

$N=3$일 때, 경우의 수는

$1\rightarrow 2\rightarrow 3$

$1\rightarrow 3$

2가지 입니다.

 

$N=4$일 때, 경우의 수는

$1\rightarrow 2\rightarrow 3\rightarrow 4$

$1\rightarrow 2\rightarrow 4$

$1\rightarrow 3\rightarrow 4$

$1\rightarrow 4$

4가지 입니다.

 

이렇게 나열해보면, $N$이 증가함에 따라 2배씩 증가하는 경우의 수를 확인할 수 있습니다.

 

다른 방법으로는, 직관적으로 징검다리의 개수가 N개일 때 경우의 수를 $X_{N}$이라고 한다면, 

 

$N+1$개의 징검다리를 건널 때

 

처음 1개를 건넌 뒤 남은 N개의 다리를 건너는 방법

징검다리를 N개 건넌 뒤 마지막 1개를 건너는 방법

 

이렇게 $X_{N+1}=2\times X_{N}$을 짐작할 수도 있습니다. (위는 수학적으로 정확한 방법은 아닙니다.)

 

이 경우에도 $X_{1}$, $X_{2}$, $X_{3}$, $\cdots$ 를 직접 구해서 올바른 식을 도출한 건지 확인할 필요성이 있습니다.

 

결과적으로 $N\geq 2$ 일 때 $X_{N+1}=2\times X_{N}$ 이고 $X_{2}=1$임을 구했으므로 다음 사실을 알 수 있습니다.

 

 $X_{N}=2^{N-2}$  (단, $N\geq 2$)

 

이를 바탕으로 다음과 같이 코드를 짤 수 있습니다.

 

#include <stdio.h>
#define mod 1000000007

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

int main() {
	int T;
	scanf("%d", &T);
	while(T--) {
		int N;
		scanf("%d", &N);
		if (N <= 2) {
			printf("1\n");
		}
		else {
			printf("%lld\n", power_modular(2, N-2));
		}
	}
	return 0;
}

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

 

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

---

사실 조합론으로도 풀 수 있는 문제입니다.

 

징검다리의 개수가 $N$일 때 $1$번 징검다리와 $N$번 징검다리를 반드시 거쳐야 하므로

 

선택할 수 있는 다리는 총 $N-2$개가 됩니다. 따라서 경우의 수는

 

$N-2$ 개의 다리 중에서 $0$개를 선택하는 경우의 수

$N-2$ 개의 다리 중에서 $1$개를 선택하는 경우의 수

$\cdots$

$N-2$ 개의 다리 중에서 $N-2$개를 선택하는 경우의 수

 

를 모두 더한 값인 $2^{N-2}$ 가 됩니다. ( 혹시 이해가 안 가신다면 $\left( 1+x \right)^{n}$ 과 이항정리의 관계를 검색해보세요. )

 

---

 

또한 위에선 아주 직관적인 방법으로 $X_{N+1}$과 $X_{N}$의 관계식을 짐작했지만

 

$X_{N+1}=X_{N}+X_{N-1}+X_{N-2}+\cdots +X_{2}+X_{1}$ 이 성립합니다.

 

(우변의 항들은 각각

$N$번 징검다리 위에 올라선 뒤   $N+1$번 징검다리로 가는 경우

$N-1$번 징검다리 위에 올라선 뒤   $N+1$번 징검다리로 가는 경우

$N-2$번 징검다리 위에 올라선 뒤   $N+1$번 징검다리로 가는 경우

$\cdots$

$2$번 징검다리 위에 올라선 뒤   $N+1$번 징검다리로 가는 경우

$1$번 징검다리 위에 올라선 뒤   $N+1$번 징검다리로 가는 경우

 

에 대응한다고 볼 수 있습니다.)

 

따라서 다음과 같이 식을 세울 수 있습니다.

 

$X_{N+1}=X_{N}+X_{N-1}+X_{N-2}+\cdots +X_{2}+X_{1}$

$X_{N}=X_{N-1}+X_{N-2}+X_{N-3}+\cdots +X_{2}+X_{1}$

 

이제 위 식에서 아래 식을 빼어 $X_{N+1}=2\times X_{N}$을 유도할 수 있습니다.

 

$X_{2}=1$ 이고 $X_{3}=2$ , $X_{4}=4$ 이므로 위 점화식은 $N\geq 2$ 에서 성립함을 알 수 있습니다.

 

따라서 $N\geq 2$ 에서 $X_{N}=2^{N-2}$ 임을 구할 수 있습니다.