[ boj : 22236 ] 가희와 비행기

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

22236번: 가희와 비행기

해설 : d 의 제한이 4000이 MAX이니 그냥 2차원 배열 넉넉하게 선언해주면 됩니다.

파스칼의 삼각형 문제 처럼 대각선에서 값들을 가져와 저장해 주면 됩니다. 이때, 조심할 점은 오버플로,,,,,,,,,조심합니다. 모듈러 연산을 해준다고 해도 덧셈 연산을 진행할때 int 형의 범위를 벗어나는 경우가 생길 수도 있습니다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[8100][8100];

void solve();

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	ll d, m;
	cin >> d >> m;
	dp[0][0] = 1;
	for (ll i = 1; i <= d; i++) {
		for (ll j = 0; j <= i; j++) {
			if (j == 0)dp[i][j] = dp[i - 1][j + 1];
			else if (j == i)dp[i][j] = dp[i - 1][j - 1];
			else {
				if (j - 1 == 0)dp[i][j] = dp[i - 1][j + 1];
				else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]);
			}
			dp[i][j] %= m;
		}
	}
	cout << dp[d][0];
}