[백준/파이썬] 1010번 다리 놓기 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1010번 다리 놓기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

서쪽 사이트 N개와 동쪽 사이트 M개가 있을 때, 겹치지 않게 다리를 놓는 경우의 수를 구하는 문제입니다.

결국 조합 M C N을 계산하면 됩니다.

코드

cases = [[0]*31 for _ in range(31)]
cases[0][0] = 1

for i in range(1, 31):
    for j in range(0, i+1):
        cases[i][j] = (cases[i-1][j-1] if j > 0 else 0) + cases[i-1][j]

for _ in range(int(input())):
    n, m = map(int, input().split())
    print(cases[m][n])

설명

파스칼 삼각형을 미리 구성해 조합값을 빠르게 꺼냅니다.

• cases[i][j] = iCj
• 점화식: iCj = (i-1)C(j-1) + (i-1)Cj

최대 범위가 작아서(<= 30) 사전 계산 후 바로 출력하면 충분합니다.

---

• 백준 문제풀이 전체 목록 보기

---