[파이썬] 백준 2775번과 파스칼 삼각형의 관계

백준 2775번 문제를 풀 때 여러가지 방법이 있겠지만 머릿속에 가장 떠오른 간단한 방법을 소개하고자 한다.

우선, 기본적인 방법으로는 노가다식으로 인원수를 한 층 한 층 구해가는 방법이 있다.

import sys
N = int(input())
for _ in range(N):
    a = int(sys.stdin.readline()) # 층 수 받아오기
    b = int(sys.stdin.readline()) # 호 수 받아오기
    old_list = [i for i in range(1,15)] # 0층의 인원수 (14가 최대라고 했으므로)
    new_list = old_list[:] # 리스트 복사
    for _ in range(a): # 입력된 층 수만큼 업데이트
        for j in range(b): # 입력된 호 수만큼 업데이트
            new_list[j] = sum(old_list[:j+1]) # 새로운 층 인원수 구하기
        old_list = new_list[:] # 한 층 올리기
    print(new_list[b-1])

위 코드도 충분히 심플하다. 하지만 a와 b가 커질수록 계산량이 늘어난다.
새로운 풀이의 인사이트를 얻기 위해 여기서 각 층의 인원수를 일단 그려보면 다음과 같다.

이것만 보면 딱히 감이 오지 않는다. 그렇다면 이렇게 바꿔본다면 어떨까?

이래도 감이 잘 오지 않는다. 그러면 층 수 컬럼도 떼어본다.

자 이제 그럼 거의 다 왔다. 위키백과에서 파스칼의 삼각형을 검색해 본다.

우리가 그려본 그림과 파스칼의 삼각형을 비교해 본다. 무언가 공통점이 발견된다.
그림을 빙글 돌려보면 다음과 같다.

(1), (1,1), (1,2,1), (1,3,3,1) ... 파스칼 삼각형이 된다.
파스칼 삼각형은 이항정리에서 계수들의 값을 계산할 때 주로 이용된다. 각 수의 계산방법은 다음과 같다.

($_0C_0$), ($_1C_0, _1C_1$), ($_2C_0, _2C_1, _2C_2$), ($_3C_0, _3C_1, _3C_2, _3C_3$) ...

이와 같은 규칙을 생각했을 때 a층 b호실의 인원수는

$_{a+b}C_{a+1} = _{a+b}C_{b-1}$

으로 표현할 수 있다(해석을 위해 위 그림에 지하 1층을 추가해주었다는 사실을 잊으면 안된다. 0층의 인원수는1,2,3,4,5...이다). 즉, 코드로 표현하면 아래와 같다.

import sys
import math
n = int(input())
for _ in range(n):
    a = int(sys.stdin.readline()) # 층 수 가져오기
    b = int(sys.stdin.readline()) # 호 수 가져오기
    print(int(math.factorial(a+b)/math.factorial(a+1)/math.factorial(b-1))) 

혹은 math.comb 함수를 이용하여도 상관없다.