[Codeup] 3701. 파스칼 삼각형

1. 문제 링크

https://codeup.kr/problem.php?id=3701

코드업

 

2. 문제 풀이

간단한 DP 문제다.

다만 n이 50이기 때문에, int 범위를 넘어가는 것을 조심해야 한다.

 

3. 아이디어

1. 파스칼 삼각형의 규칙을 파악하는 것이 중요하다.
2. 양 끝은 1로 시작하고 내부의 수는 바로 위 행의 인접한 두 수의 합 형태가 된다는 것을 알면 쉽게 구할 수 있다.
3. 점화식은 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]; 과 같은 형태로 구할 수 있다.

 

 

4. 구현

※ C++ Source Code

#include <iostream>
using namespace std;
long long int pascal[55][55];
int main(void)
{
	int n;
	cin >> n;
	
	pascal[1][1] = 1;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= i; j++) 
		{
			pascal[i][j] = pascal[i - 1][j] + pascal[i - 1][j - 1]; 
			// dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			cout << pascal[i][j] << " ";
		}
		cout << endl;
	}
}