[DP] 백준 11051. 이항계수2 (feat. 파스칼의 삼각형)

이항계수를 구하는 문제

n과 k 가 주어질 때, 두 수에 해당하는 이항계수를 구하는 것이 문제이다.

관건은 이항계수의 개념을 알고, 이를 코드로 구현하는 것이다.

(단, 수의 범위가 1,000으로 그렇게 크지 않기 때문에 전체 숫자를 구한 다음에 접근하는 방법도 가능하다.)

 

이항계수 이해하기

조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

 

위의 이항계수 주요성질을 참고해, 코드를 구현할 수 있다. 정의식 (n)! / (n-k)!(k)! 을 이용하거나, 1 또는 2를 이용해 재귀함수나 dp를 사용한 코드를 볼 수 있다. (맨 밑 참고 블로그 확인)

아래의 코드는 bottom-up으로 파스칼의 삼각형의 값을 다 채워서 접근하는 방식이다. n k 를 구하기 위해 dp 테이블의 전항을 이용한다.

두 가지 코드

d = [[0]*1 for _ in range(1001)]
d[1].append(1) # 이거 왜? => 파스칼 삼각형 보면 시작을 1로 함. 초기값 넣어주는 것

for i in range(2,1001):
    for j in range(1, i+1):

        if i == j or j == 1:
            d[i].append(1)
        else:
            d[i].append(d[i-1][j-1] + d[i-1][j])

print(d[n+1][k+1]%10007)

참고블로그

파스칼의 삼각형을 코드로 구현한 모습

 

파스칼의 삼각형, 이항계수를 그림으로 표현한 것

 

 

N, K = map(int, input().split())
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(0, N+1):
    for j in range(0, N+1):
        if j == 0:
            dp[i][j] = 1
        elif i == j:
            dp[i][j] = 1
        elif j == 1:
            dp[i][j] = i
        elif N >= K:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]


print(dp[N][K] % 10007)

 

 

2번 코드는 이항계수 개념 배우고 다른 문제 한 것처럼 했으면 풀 수 있었을 거 같은데,

1번 코드는 파스칼의 삼각형을 기반으로 구현한 것에 가깝달까.!

@ㅅ@ 어려웠다

 

---

22. 6. 3 update

n = 7
k = 3
dp = [[0]*(n+1) for _ in range(n+1)]

def getDP(i,j):
    if i < j :
        return
    if i == j or j == 1:
        return 1
    if dp[i][j] == 0:
        dp[i][j] = getDP(i-1, j-1) + getDP(i-1,j)
    return dp[i][j]

for i in range(1,n):
    for j in range(1,i+1):
        print(getDP(i,j), end = ' ')
    print()

print(getDP(n,k))

함수 호출과 dp를 엮어서 다시 풀어봤다.

아래 for문은 눈으로 확인하고 싶어서 출력해본 것.

 

이항계수 이해하기 참고 블로그1

이항계수 이해하기 참고 블로그2