[BAE/<JOON> 문제풀이] 14945. 불장난

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

14945번: 불장난

핵심::
DP가 아니라 초반 답 보고 규칙을 찾으면 된다.

풀이::
초반 답을 나열 해보면 이항 계수가 나온다.

의견::
2명이 갈 수 있는 위치 DP로 추적해야하는 문제인줄 알고 삽질했는데 진짜 끝이 없다.

꿀문젠줄 알고 풀었는데 10시 넘어서 품..

코드::

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	n *= 2; n -= 1;
	vector<vector<int>> arr(n + 1, vector<int>(n + 1));
	arr[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		arr[i][1] = 1; arr[i][i] = 1;
		for (int j = 2; j < n; j++) {
			arr[i][j] = (arr[i - 1][j] + arr[i - 1][j - 1]) % 10007;			
		}
	}

	cout << arr[n][n / 2 + 1];

	return 0;
}