문제 링크

https://www.acmicpc.net/problem/13703

사용 언어

C++

소스

#include <iostream>
using namespace std;
  
int k, n;
long long C[128][64];
  
int main()
{
	cin >> k >> n;
	for(int i = 1; i <= k+n; i++){
		C[i][0] = 1;
	}
	for(int j = 1; j <= n; j++){
		for(int i = 1; i <= k+n; i++){
			C[i][j] = C[i-1][j-1] + C[i+1][j-1];
		}
	}
	cout << C[k][n];
}

논리

만약 모든 경우의 수에 대해 n초 후 수면보다 밑인지 아닌지 판단하여 경우의 수를 센다면,

시간 복잡도는 O(2ⁿ)이다.

당연히 이런 알고리즘을 사용하면 시간초과 에러를 만나게 된다.

k, n일 때 살아남는 경우의 수를 C[k, n]이라 하자.

이 상황에서 물벼룩은 위 또는 아래로 이동할 수 있다.

위로 갔을 경우 살아남는 경우의 수는 C[k-1, n-1]이고

아래로 갔을 경우 살아남는 경우의 수는 C[k+1, n-1]이다.

즉, C[k, n] = C[k-1, n-1] + C[k+1, n-1] 임을 알 수 있다.

자 위와 같은 점화식을 통해 우리는 동적 프로그래밍을 사용하면 된다는 것을 알아냈다.

초기값으로 C[0, 0] = 0 그리고 C[i, 0]=1을 주도록 한다.

그 후, 위 코드와 같은 논리를 통해 C[k, n]의 값을 찾아낸다.

시간복잡도는 O(n*k) 이다.

참고로 표로 보면 아래와 같다. k=2, n=3에 대해 계산과정을 표로 나타내었다.