[백준 16395번] 파스칼의 삼각형 (feat. NodeJS)

16395번: 파스칼의 삼각형

파스칼 삼각형의 어떤 항목의 값은 해당 항목의 위쪽 두 개 항목 값의 합이다.

결국 모든 항목들은 같은 공식으로 이루어져있고, 이것을 분할 정복과 기저 조건을 사용하는 재귀로 풀 수 있다.

 

분할 정복 : 어떤 항목의 값은 해당 항목의 위쪽 두 개 항목 값의 합이므로, 이 공식을 사용하여 알고리즘을 작성한다.

기저 조건 : 행이 1이면 1을 반환하고, 행과 열이 1이면 1을 반환한다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().split(" ");
const [row, col] = input.map((value) => parseInt(value));

const pascalTriangle = (row, col) => {
    if (col === 1) {
        return 1;
    } else if (row === col) {
        return 1;
    } else {
        return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
    }
};

const init = () => {
    const result = pascalTriangle(row, col);
    console.log(result);
};

init();