[백준][C++] 16395 파스칼의 삼각형

16395. 파스칼의 삼각형

16395번: 파스칼의 삼각형

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

파스칼의 삼각형 문제!

파스칼의 삼각형 개념을 로직으로 옮기면 되는 간단한 문제였다.

알고리즘 설계

1. N층에 있다면, 1번째와 N번째 요소는 1로 만들어준다.
2. 현재 M번째라고 하면, 그 외에 요소는 arr[N-1][M-1] + arr[N-1][M]
3. 입력 층까지 반복한다.

코드

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int dp[30][30], y, x;
    cin >> y >> x;

    for (int i = 0; i < 30; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (i > 0 && j > 0 && j != i)
            {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
            else
            {
                dp[i][j] = 1;
            }
        }
    }

    cout << dp[y - 1][x - 1];
}

 

조합과 연관이 되어있어서 더 신기했던 문제이다.

다른 조합 문제들을 이렇게 풀었으면 어땠을까하는 생각이 들었다.