[백준/c++] 16395번 파스칼의 삼각형

16395번 문제 링크

문제

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다.

단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

N번째 행에는 N개의 수가 있다.
첫 번째 행은 1이다.
두 번째 행부터, 각 행의 양 끝의 값은 1이고, 나머지 수의 값은 바로 위 행의 인접한 두 수의 합이다.
예를 들어, n=3이면 3번째 행의 2번째 수는 위 행의 인접한 두 수 (1과 1)을 더해서 만든다.

n=6일 때, 파스칼 삼각형의 6번째 행의 10은 5번째 행의 인접한 두 수(4와 6)을 더해서 구한다.

정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n번째 행에서 k번째 수를 출력하는 프로그램을 작성하시오. 이때, 이 수는 이항계수 C(n-1,k-1)임에 주의하시오.

입력

첫째 줄에 정수 n과 k가 빈칸을 사이에 두고 차례로 주어진다. 이 때, 1 ≤ k ≤ n ≤ 30을 만족한다.

출력

첫째 줄에 n번째 행에 있는 k번째 수를 출력한다.

풀이

n 과 k 가 주어질 때 해당 값은
(n-1, k-1) 위치에 있는 값 + (n-1, k) 위치에 있는 값을 더하면 구할 수 있다. 소스 코드도 이 공식을 토대로 계산하면 쉽게 구할 수 있다.

파스칼의 삼각형 관련 포스팅 은 👉 [알고리즘] 파스칼의 삼각형 를 참고하면 된다.

소스코드

#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
    int n,k;
    
    cin >> n >> k;
    
    int pascal_arr[n][k];  // 파스칼 삼각형 수가 저장되는 배열
    
    // 삼각형에서 맨 처음 값은 1로 고정임
    for (int i = 0; i < n; i++) pascal_arr[i][0] = 1;
    
    for(int i=1;i<n;i++) {
        for(int j=1;j<=i;j++) {
            if (j >= k) continue; // k 이상으로는 값을 구할 필요가 없기 때문에 continue 로 넘겨줌
            pascal_arr[i][j] = pascal_arr[i-1][j-1];
            
            // 행 마지막 값인 경우에는 왼쪽 위에 있는 값만 더해주고
            // 그게 아닌 경우에는 왼쪽 위, 오른쪽 위에 있는 값을 더해준다.
            // 해당 조건이 없는 경우 빈 배열에 있는 쓰레기 값이랑 더해져서 데이터가 정상적으로 나오지 않음
            if (i-1 >= j) pascal_arr[i][j] += pascal_arr[i-1][j];
        }
    }
    
    cout << pascal_arr[n-1][k-1];
}

간단하게 (1,1) 부터 입력 받은 값까지 왼쪽 위와 오른쪽 위 값을 더하면서 내려오는 코드다

정답