[TIL] 알고리즘 풀이

다리 놓기

https://www.acmicpc.net/problem/1010
동적 계획법 풀이

const fs = require('fs')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')

const [n, ...tests] = input

const dp = []
for (let i = 0; i < 30; i++) {
    const array = []
	for (let j = 0; j < 30; j++) {
        array.push(0)
	}
	dp.push(array)
}

for (let i = 1; i < 30; i++) {
    dp[i][0] = 1
	dp[i][i] = 1
}

for (let i = 1; i < 30; i++) {
    for (let j = 1; j < i; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
	}
}

let answer = ''
for (let i = 0; i < +n; i++) {
    const [k, n] = tests[i].split(' ').map(x => +x)
    answer += dp[n][k] + '\n'
}

console.log(answer)

이 외 풀이들:
https://github.com/fancyers/coding-test

조합과 순열
https://velog.io/@effort_jk/JavaScript-%EC%A1%B0%ED%95%A9%EA%B3%BC-%EC%88%9C%EC%97%B4

이항계수 알고리즘
https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients