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


a_{n1} = 1
a_{nn} = 1
a_{nk} = a_{{n-1}{k-1}} + a_{{n-1}{k}} (n, k>=0)

구하는 점화식은 위와 같이 나타냅니다. 이런식으로 점화식을 구하여 부분 문제를 풀어가며 전체 문제의 해답을 찾아내는 방식을 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;

}

신고

+ Recent posts