문제
재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)
재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
출력
각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.
예제 입력
3
2 2
1 5
13 29
예제 출력
1
5
67863915
내가 했던 풀이 방법
조합을 이용해서 풀이한다. 조합은 순서를 신경쓰지 않기 때문에 서쪽에 가장 위 사이트가 선택된 동쪽 사이트 중 가장 위에 있는 것을 선택하면 다리가 서로 겹쳐지지 않게 된다.
문제 사진을 예시로 설명하면 서쪽 사이트를 위에서부터 1, 2, 3, 4로 하고 동쪽 사이트를 1, 2, 3, 4, 5, 6, 7로 뒀을 때 동쪽 사이트에서 4개를 겹치지 않고 선택할 수 있는 방법은 7C4이다. 그 중 하나의 경우인 (1, 3, 5, 7)이 선택됐다고 할 때 "서쪽-동쪽"으로 표현하면 1-1, 2-3, 3-5, 4-7을 선택하게 되면 다리가 겹치지 않게 된다.
하지만 조합을 그대로 계산하게 되면 값이 매우 커지게 된다. BigInt를 사용해야 할 것이다. 그리고 문제에서 시간 제한을 0.5초로 두었기 때문에 빠르게 계산할 필요가 있다. 이를 위해 조합의 특징(파스칼의 삼각형)을 재귀를 이용해 계산해줄 것이다.
파스칼의 삼각형
파스칼의 삼각형으로 알 수 있는 조합의 특징은 아래와 같다.
즉 이 특징을 재귀를 이용해서 조합을 구현하면 된다.
- C를 31×31 크기의 0으로 채워진 2차원 배열로 선언해준다. 1C0과 1C1을 1로 초기화해준다. (초기화과정은 생략해주어도 된다. 조건문에 의해 해당 값은 1로 저장될 것이다.)
- T(테스트케이스 수)만큼 반복하며, N과 M을 combination 함수의 인자로 전달해준 값을 출력한다.
- combination에서는 C[n][r]이 0보다 클 경우 즉, 값이 저장된 경우 해당 값을 return 해준다. 만약 r이 0이거나 n과 같을 경우, C[n][r]을 1로 return 해준다. 두 경우가 아닌 경우, C[n][r]을 C[n-1][r-1]+C[n-1][r]로 return 해준다. 이때, C[n-1][r-1]과 C[n-1][r]을 구하기 위해 재귀를 사용한다. (경우의 따라 nCr의 값이 달라지지 않는다. 즉, 어떤 경우에도 조합의 값은 같다. 그렇기 때문에 C를 테스트 케이스마다 초기화해줄 필요가 없다. 오히려 하지 않는 것이 연산 속도에 좋다.)
코드
const fs = require('fs');
let [T, ...input] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
let N = 0;
let M = 0;
let C = Array.from({ length: 31 }, () => Array.from({ length: 31 }).fill(0));
C[1][0] = 1;
C[1][1] = 1;
function combination(n, r) {
if (C[n][r] > 0) {
return C[n][r];
}
if (r === 0 || r === n) {
return (C[n][r] = 1);
} else {
return (C[n][r] = combination(n - 1, r - 1) + combination(n - 1, r));
}
}
for (let i = 0; i < Number(T); i++) {
N = Number(input[i].trim().split(' ')[0]);
M = Number(input[i].trim().split(' ')[1]);
console.log(combination(M, N));
}회고
파스칼의 삼각형........을 다 까먹었기에 이 문제는 처음부터 다른 사람의 풀이를 참고할 수 밖에 없었다. 조합을 계산하는 방법은 알았지만 당연히 그 방법은 Number에 범위에서 벗어나며 시간초과가 날 것 같았기 때문에 다르게 풀이하는 방법이 있어야 한다고 생각했다. 그렇게 찾아본 결과 기초적인 지식이 없었으면 손대기도 어려웠을 것 같았다. 역시 고등학교 때 수학을 계속 기억하고 있어야 했는데 너무 다 소멸시킨 것 아닌지... 수학을 다시 공부해야 할 것 같았다. 조합 관련 문제를 많이 풀어서 다음에 유사한 문제가 나오면 이 문제를 떠올릴 수 있도록 해야겠다.
