[백준] 16395: 파스칼의 삼각형(C++)

문제

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

풀이

삼각형 형태를 좌측 정렬하여 2차원 배열로 생각해서 푸면 되는 문제이다.

 

배열을 pascal[i][j]이라고 가정할 때, j = 0, j = i인 경우에는 모두 1을 저장한다.

그 외의 값들은 위 행의 인접한 두 수를 더하면 되는데, 2차원 배열이므로 식을 아래처럼 만들 수 있다.

 

pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

 

코드

#include <iostream>

using namespace std;

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

	int n, k;
	cin >> n >> k;

	int pascal[31][31];

	for (int i = 0; i < n; i++) {
		pascal[i][0] = 1;
		pascal[i][i] = 1;

		if (i < 2)	//행이 2보다 작을 때는 1밖에 없다
			continue;

		for (int j = 1; j < i; j++) {
			pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
		}
	}

	cout << pascal[n - 1][k - 1];

	return 0;
}