백준 16395 - 파스칼의 삼각형 ( C++ )

안녕하세요 besforyou입니다

 

백준 16395 - 파스칼의 삼각형 문제 풀이를 설명하겠습니다

---

문제 풀이

 

동적 계획법 (Dynamic Programming)을 사용해야 합니다. 일일이 다 구하려 하지 마시고, 주어진 n값만큼의 행을 가진 파스칼 삼각형을 메모이제이션(memoization)으로 구한 뒤 n행 k번째 값을 출력해주기만 하면 됩니다.

 

 

파스칼 삼각형 만드는 법

 

2차원 배열 mat을 선언하고 

 

파스칼 삼각형의 (왼쪽에서부터 1번 )

1행 1번 -> mat [1][1]

2행 1번 -> mat [2][2] , 2행 2번 ->  mat [2][1]

3행 1번 -> mat [3][3], 3행 2번 -> mat [3][2], 3행 3번 -> mat [3][1]

.

.

.

 

방식으로 파스칼의 삼각형을 생성하면 됩니다.

 

 

코드

 

#include <iostream>
 
using namespace std;
 
int mat[32][32];
 
int main (void) {
 
    int n,k;
    cin >> n >> k;
 
    for ( int i = 1; i <= n ; i++ ) {
        for (int j = 1 ; j <= i ; j++ ) {
            if ( j == 1 || i == j) {
                mat[i][j] = 1;
            }
            else {
                mat[i][j] = mat[i-1][j-1] + mat[i-1][j];
            }
        }
    }
 
    cout << mat[n][k];
    return 0;
}