취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24418번 문제인 알고리즘 수업 - 행렬 경로 문제 2이다.
문제는 아래 링크를 확인하자.

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

기본적인 풀이 방법은 행렬 경로 문제 1과 같다.

위의 문제 풀이에 더해 파스칼의 삼각형을 구현할 때 나머지연산을 추가하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int comb[2000][2000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 2000; i++) comb[i][0] = comb[i][i] = 1;
	for (int i = 2; i < 2000; i++) {
		for (int j = 1; j < i; j++) comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j])%1000000007;
	}

	int N; cin >> N;
	cout << (2 * comb[2 * N - 1][N]) % 1000000007 << ' ' << N * N;
}