SW Expert Academy 2005 파스칼 삼각형

문제 출처 (opens new window)

• 풀이 방법 및 배워야할 것:

  • DP로 해결했으나 N의 갯수가 작고 어차피 처음부터 다 풀어야 되므로 굳이 DP를 쓰지 않아도 된다.

• 풀이 코드 :

#include<iostream>
 
using namespace std;
 
int a[11][11];
 
int pascal (int x, int y){
     
    if (x==1) {
        return a[x][y]=1;       
    }
     
    if (y==1){
        return a[x][y]=1;
    }
    if (y==x){
        return a[x][y]=1;
    }
     
    if (a[x][y]!=0){
        return a[x][y];
    }
     
    return a[x][y]=pascal(x-1,y-1)+pascal(x-1,y);
     
}
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;
     
    for(test_case = 1; test_case <= T; ++test_case)
    {
 
        int n;
        cin >> n;
        cout << "#" << test_case<< "\n";
         
        for (int i=1;i<=n;i++){
            for (int j=1;j<=i;j++){
                cout << pascal(i,j) << " ";
            }
            cout << "\n";
        }
 
    }
    return 0;
}