백준(baekjoon) 11051번: 이항 계수 2(실버 3, 파이썬 PYTHON) - 정수론 및 조합론

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

import sys

N,K=map(int,sys.stdin.readline().split())
dp=[[1 for _ in range(K+1)]for _ in range(N+1)]

for x in range(2,N+1):
  for y in range(1,min(x,K)+1):
    if(x!=y):  
      dp[x][y]=(dp[x-1][y-1]+dp[x-1][y])%10007 
    
print(dp[N][K])

 

※ 정수론 및 조합론

 

 

● 이 문제는 파스칼의 삼각형을 활용하여 동적 계획법으로 해결할 수 있다.

 

● 먼저 인덱스 0~N 까지의 행, 0~K  까지의 열로 이루어진 2차원 배열 dp를 생성한다.

 

● 행 0,1 의 배열 요소는 모두 1이므로 건너 뛰고 행 인덱스 2부터 연산을 시작한다.

이 때, 각 행에서 열 인덱스가 0 이거나 그 행의 인덱스와 같을 시 그 요소는 1이므로 연산을 생략한다.

 

● 그 외에는 현재 요소를 그 전 행과 그 전 열의 요소와 그 전 행과 같은 열의 요소를 합한 값으로 갱신해주면 값을 도출해낼 수 있다.

 

 

결과

 

 

♣ 참고: 파스칼의 삼각형

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전

 

♣ 참고: 동적계획법

 https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 위키백과, 우리 모두의 백과사전