파스칼의 삼각형 소스코드

파스칼의 삼각형이란 아래 사진과 같이 이항계수를 삼각형 모양의 기하학적 형태로 배열한 모양을 듯합니다.

 ()

구하는 점화식은 위와 같이 나타냅니다. 이런식으로 점화식을 구하여 부분 문제를 풀어가며 전체 문제의 해답을 찾아내는 방식을 dp라고 하죠 ㅎㅎ 

아래는 n을 입력하면 처음부터 n번째 줄 까지의 파스칼의 삼각형을 구하는 예제 소스입니다

/* 파스칼의 삼각형 구하는 예제(dp) */

#include <iostream>

using namespace std;

 

int arr[100][100] = {0, };

 

int main(){

        int n;

        cin >> n;

        for(int i=0; i<n; i++){

               for(int j=0; j<=i; j++){

                       if(i == 0 || j == 0){

                              arr[i][j] = 1;

                       }

                       else{

                              arr[i][j] = arr[i-1][j] + arr[i-1][j-1];

                       }

               }

        }

 

        for(int i=0; i<n; i++){

               for(int j=0; j<=i; j++){

                       cout << arr[i][j] << " ";

               }

               cout << endl;

        }

 

        return 0;

}