조합

문제

백준 2407번 - 조합

언어

JavaScript

순서도

다이나믹 프로그래밍 기법으로 파스칼의 삼각형 만들기
파스칼의 삼각형에 기반해서 주어진 N 과 K 의 조합 구하기

문제 풀이 step 1

본 문제는 백준 11051번 - 이항 계수 2 풀이 에서 알아봤던 파스칼의 삼각형을 이용하면 쉽게 풀 수 있습니다.
만약 파스칼의 삼각형이 생소하시다면 백준 11051번 - 이항 계수 2 문제를 먼저 풀어보시는 것을 추천드립니다.
파스칼의 삼각형의 간단하게 설명하자면, 조합 (NCK) 을 삼각형 모양의 기하학적 형태로 배열한 것입니다. 이때 각 요소가 조합의 값을 의미하고 있습니다.
파스칼의 삼각형을 만드는 방법은
1. 먼저 첫 번째 줄에는 숫자 1 을 씁니다.
2. 그 다음 줄을 만들려면, 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더합니다.
만드는 방법을 수학 식으로 나타내면
- a[n][1] = 1;
- a[n][n] = 1;
- a[n][k] = a[n-1][k-1] + a[n-1][k] (단, n, k >= 0)
위의 수학식을 점화식으로 생각하고 다이나믹 프로그래밍 기법으로 파스칼의 삼각형을 만듭니다.
이때, 값이 너무 커질 수 있으므로 BigInt 를 사용하도록 합니다. 출력할 때는 String 형으로 변환하면 됩니다.
- a[n][1] = 1n;
- a[n][n] = 1n;
- a[n][k] = a[n-1][k-1] + a[n-1][k] (단, n, k >= 0)
그리고 문제에서 주어진 N 과 K 로 파스칼의 삼각형에 접근해서 조합값 (NCK) 을 출력하면 정답이 됩니다.
추가 설명은 주석으로 작성하겠습니다.

Reference.

위키백과 - 파스칼의 삼각형

후기

이항 계수 2 문제를 먼저 풀어봐서 쉽게 풀 수 있었습니다.
BigInt 로 파스칼의 삼각형을 만들고 Number 형으로 변환해서 출력했는데 틀렸습니다.
아무래도 값이 너무 크기 때문에 Number 형으로 변환하는 과정에서 값이 조금 달라졌던 것 같습니다. 따라서 String 형으로 변환하는 것이 값을 올바르게 보존하며 변환할 수 있습니다.

소스 코드

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

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);

	// 파스칼의 삼각형 구하기
	const arr = Array.from({length: 101}, () => []);
	for (let i = 1; i < 101; i++) {
		arr[i][0] = arr[i][i] = 1n;
		for (let j = 1; j < i; j++) {
			arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
		}
	}

	// BigInt 형을 String 형으로 변환해서 출력
	return String(arr[n][m]);
};

console.log(solution(input));