[C++, python] 백준 16395번 풀이 ( 파스칼의 삼각형 )

- 문제 ( 16395번 ) : 파스칼의 삼각형

• 링크 : https://www.acmicpc.net/problem/16395

• 정수 n과 k가 주어졌을 때 파스칼의 삼각형에 있는 n 번째 행에서 k 번째 수를 출력하는 프로그램을 작성하시오.

  • 이 때, 출력하는 수는 이항계수 C(n-1, k-1) 임.

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 정수 n 과 k 가 빈칸을 사이에 두고 차례로 입력. ( n은 몇번째 행인지, k는 몇번째 열인지 )
  ( 1 ≤ k ≤ n ≤ 30 )

[ 출력 ]

• 첫째 줄에 n번째 열에 있는 k번째 수를 출력.

---

- 문제 풀이

• 이번 16395 번 파스칼의 삼각형 문제는 파스칼의 삼각형을 배열로 만든 후 입력받은 위치에 있는 값을 출력하면 되는 아주 간단한 문제이다.

  파스칼의 삼각형을 만들 때 문제에서 주어진 수식을 사용해서 만든다.

  • 수식 : p[n][k] = p[n-1][k-1] + p[n-1][k]

  이렇게 구한 후 문제에서 주어진 것처럼 C(n-1, k-1) 의 값을 출력하면 문제 해결!

• 문제 해결 방법을 정리하면 다음과 같다

  • step1) 30 * 30 size 의 배열 생성하며 1로 초기화 ( pascal 삼각형 )
  • step2) 2번째 줄부터 파스칼 삼각형의 수식을 활용해 배열 채우기.
  • step3) 사용자에게 n, k 의 값 입력받기
  • step4) pascal[n-1][k-1] 의 값 출력

---

- 최종 코드

• c++ code

#include <iostream>
using namespace std;

// global variables
int arr[31][31] = {0, }; // pascal triangle

// make pascal triangle ( C(n, k) = C(n-1, k-1) + C(n-1, k) )
void mk_pascal() {
  // step1. col = 1 : fill with 1
  for(int i = 0; i < 31; i++) {
    arr[i][0] = 1;
  }

  // step2 . fill the values up to the current position
  for(int i = 1; i < 31; i++) {
    for(int j = 1; j <= i; j++) {
      arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
    }
  }
}

// print arr (To check)
void print_arr() {
  for(int i = 0; i < 31; i++) {
    for(int j = 0; j < 31; j++) {
      cout << arr[i][j] << " ";
    }
    cout << endl;
  }
}


// entry program
int main() {

  // input n, k
  int n = 0; // number of rows
  int k = 0; // number of cols
  cin >> n >> k;

  // create pascal triangle
  mk_pascal();

  // print pascal
  // print_arr();

  // print result
  cout << arr[n-1][k-1] << endl;

  return 0;
}

• python code

# step1. create pascal triangle
# 1-1. fill with 1 
pascal = [[1 for _ in range(i)] for i in range(1, 31)]

# step2. fill the value (c[n][k] = c[n-1][k-1] + c[n-1][k])
for i in range(2, 30): # i = 2 to 29
  for j in range(1, i): # j = 1 to i
    pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

# step3. input n, k
n, k = map(int, input().split())

# step4. print result
print(pascal[n-1][k-1])