[백준] 알고리즘 16395번 - 파스칼의 삼각형 문제

문제

www.acmicpc.net/problem/16395

16395번: 파스칼의 삼각형

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[31][31];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,k;
	cin >> n >> k;
	dp[1][1] = 1, dp[2][1] = 1, dp[2][2] = 1;
	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= k; j++) {
			if (j == 1 || j == i) dp[i][j] = 1;
			else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
		}
	}
	cout << dp[n][k];
}

풀이

삼각형을 옆으로 쭈욱 밀어버리면 간단하게 생각할 수 있다.

어짜피 배열은 이렇게 담길테닌간

가장자리 부분은 1로 처리해주고 그 사이 값들은 이전 행의 값들을 순서대로 더해준다.