[바미] 다리 놓기

문제

 

 

https://www.acmicpc.net/problem/1010

코드

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

const T = parseInt(input[0], 10);

// 이항 계수를 동적 프로그래밍으로 계산하는 함수
function binomialCoefficient(n, k) {
    const dp = Array.from(Array(n + 1), () => Array(k + 1).fill(0));

    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= Math.min(i, k); j++) {
            if (j === 0 || j === i) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }

    return dp[n][k];
}

let result = [];

for (let i = 1; i <= T; i++) {
    const [N, M] = input[i].split(' ').map(Number);
    result.push(binomialCoefficient(M, N));
}

console.log(result.join('\n'));

문제 해설

\[이 문제는 주어진 두 수 N과 K에 대해 이항 계수 \binom{N}{K}를 계산하는 문제입니다.

 

그러니까 이항 계수는 조합combination의 수를 나타내며, 이는 특정 수 N개에서 K개를 선택하는 방법의 수를 의미하는데 주어진 N과 K의 범위 내에서 다리를 지을 수 있는 경우의 수를 계산하는 문제죠.\]

 

이항 계수는 수학적으로 다음과 같이 정의됩니다만,

\[ \binom{N}{K} = \frac{N!}{K!(N-K)!} \]

이 문제에서는 동적 프로그래밍(DP)을 사용하여 풀면 중복 계산을 피할 수 있기 때문에 더 효율적으로 이항 계수를 계산할 수 있습니다.

 

DP의 점화식은 다음과 같습니다.

 \[ \binom{N}{K} = \binom{N-1}{K-1} + \binom{N-1}{K} \]

 

이랬을 때 기본 조건은 다음과 같습니다.

• \[ \binom{N}{0} = 1 \quad \text{(어떤 수에서도 0개를 선택하는 경우의 수는 1)} \]
• \[ \binom{N}{N} = 1 \quad \text{(N개에서 N개를 모두 선택하는 경우의 수는 1)} \]

그래서 binomialCoefficient(n, k)` 함수는 동적 프로그래밍을 사용하여 이항 계수를 계산하도록 만들었습니다.

2차원 배열 dp를 초기화하여 필요한 모든 부분 문제의 해를 저장하고, 기본조건 \binom{N}{0} = 1과 \binom{N}{N} = 1을 설정합니다.

 

그 후 점화식 \binom{N}{N} =  \binom{N-1}{K-1} +  \binom{N-1}{K}을 사용하여 배열에 채워줍니다.

 

그리고 각 테스트 케이스에 대해 서쪽 사이트 수 𝑁과 동쪽 사이트 수 𝑀을 읽어온 뒤, 각 테스트 케이스에 대해 이항 계수를 계산하여 결과 배열에 추가합니다.

 

그 후 결과 배열의 값을 줄 단위로 출력해 주는 형태입니다.

 

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

이 코드의 시간 복잡도는 주로 이항 계수를 계산하는 부분에서 결정되는데 동적 프로그래밍을 사용하여 이항 계수를 계산하는 시간 복잡도는 𝑂(𝑛×𝑘)입니다. 

 

따라서 각 테스트 케이스에 대해 이항 계수를 계산하는데 걸리는 시간은 𝑂(𝑀×𝑁)가 됩니다. 

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

동적 프로그래밍을 위한 2차원 배열 dp를 사용하며, 공간 복잡도는 𝑂(𝑛×𝑘)이 됩니다.

주어진 N과 M의 최대 값이 30이므로, 배열의 크기는 최대 30×30이 됩니다. 

이 수치는 메모리 제한 내에서 충분히 처리할 수 있는 크기입니다.