파스칼의 삼각형 공식

C(n,k)=C(n−1,k−1)+C(n−1,k) (n>=k)

• 조합 문제는 파스칼의 삼각형 구조와 성질을 그대로 따른다.

• 조합 문제에 dp를 적용하거나 재귀로 파스칼의 삼각형 공식이 유용하게 적용된다.

  • 이전의 두 조합 값을 더한 값으로 계산.

• 예를 들어, C(4,2)를 구한다면

C(4,2)=C(3,1)+C(3,2)

C(3,1)=C(2,0)+C(2,1)C(3, 1) = C(2, 0) + C(2, 1)

C(3,1)=C(2,0)+C(2,1)

C(3,2)=C(2,1)+C(2,2)C(3, 2) = C(2, 1) + C(2, 2)

C(3,2)=C(2,1)+C(2,2)

동적 계획법(DP)을 사용한 해결

• 파스칼의 삼각형을 활용한 조합 문제는 DP에 적용할 수 있다.
• C(n, k) 값을 미리 저장하고, 이를 재사용함으로써 중복 계산을 방지

[백준 1010]

function run(inputs: string[]) {
  const result = [];

  for (const input of inputs) {
    const [a, b] = input.split(' ').map(Number);
    console.log(a, b);

    const dp: number[][] = Array.from({ length: b + 1 }, () =>
      Array(a + 1).fill(-1),
    );

    function combination(num1: number, num2: number): number {
      if (num2 === 0 || num1 === num2) return 1;
      if (dp[num1][num2] !== -1) return dp[num1][num2];

      dp[num1][num2] =
        combination(num1 - 1, num2 - 1) + combination(num1 - 1, num2);
      return dp[num1][num2];
    }

    const comb = combination(b, a);
    result.push(comb);
  }

  return result.join('\\n');
}