[백준/Python]11050: 이항 계수 1

문제

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

백준 단계별로 풀어보기 - 조합론

---

풀이

자연수 N과 K가 주어졌을때, 이항계수 (n/k)를 구하는 문제.

 

이항계수 (n/k)는 nCk 와 같다.
nCk = n!/(k!(n-k)!)

 

단순 반복문 사용

# 메모리: 31120KB / 시간: 36ms

# 1
N, K = map(int, input().split())

ret = 1

# 2
for i in range(K):
    ret *= (N - i)

# 3
for i in range(1, K+1):
    ret //= i

print(ret)

n! = (n * (n-1) * ... * (n-k+1)) * (n-k)!
이걸 다시 공식에 적용해서,
nCk = (n * (n-1) * ... * (n-k+1)) * (n-k)! / (k! * (n-k)!)
nCk = (n * (n-1) * ... * (n-k+1)) / k!
즉, nCk = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 2 * 1)가 된다.

1. map()으로 N과 K값을 할당해주고, 결과값을 저장할 ret을 1로 할당한다.
2. 첫번째 for문: (n * (n-1) * ... * (n-k+1))
   
   • 0부터 K-1까지 i로 반복.
   • ret에 N-i를 곱한 후 재할당.
3. 두번째 for문: / (k * (k-1) * ... * 2 * 1)
   • 1부터 K까지 i로 반복.
   • 첫번째 for문을 거친 ret을 i로 나눈 뒤 재할당.

 

동적 프로그래밍(DP) 사용

# 메모리: 31120KB / 시간: 40ms

# 1
def dynamic_programming(n, k):
    # 2
    dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

    # 3
    for i in range(n+1):
        for j in range(k+1):
            if j == 0 or j == i:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

    return dp[n][k]

# 4
N, K = map(int, input().split())
print(dynamic_programming(N, K))

1. 동적 프로그래밍을 위한 함수를 생성해준다.
   파라미터는 (전체 집합의 수, 선택할 원소의 수) 로 설정한다.
2. (n+1) x (k+1) 크기의 2차원 배열 dp를 생성한다.
3. 0부터 n까지 i로 반복, 0부터 k까지 j로 순회하며 아래의 과정을 반복한다.
   • 만약 j(열)이 0이거나 i일경우(=아무것도 선택하지 않거나, 모두 다 선택할경우),
     dp[i][j]의 값을 1로 저장한다.
   • 아니라면 dp[i][j]의 값을 dp[i-1][j-1] + dp[i-1][j]로 저장한다.
   • 현재 이항계수 = 바로 위 행의 두 이항계수의 합 (파스칼의 삼각형 원리)
     
     반복을 마치면 dp[n][k]에 해당하는 값을 반환한다.
4. N, K를 map()으로 각각 할당한 후, 함수에 넣어 실행한 결과값을 출력한다.

 

이 방법은 주어지는 수가 커질수록 효율적이라고 한다.
실제로 실행시간은 단순반복을 사용한 코드가 4ms 더 빨랐다.

---

(참고) 파스칼의 삼각형

오늘먹은것도 기억안나는 판국에 파스칼의 삼각형이 기억날리가...

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

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