[Python] 2407번 조합

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

2407번: 조합

---

 

22/09/17

 

 

이 문제는 파이썬의 강점을 제대로 보여주는 문제로, 다른 언어에 비해서 큰 수 연산이 뛰어나고 지원하는 함수가 많다는 장점을 매우 잘 살릴 수 있는 문제다. 

---

 

문제 접근 방식:

 

 

여러 방식으로 풀 수 있지만, 나는 문제에서 의도하는 바 대로 풀고자 했다.

 

사실 제일 간단한 풀이는 파이썬의 math 모듈에서 지원하는 factorial함수를 사용하여 combination의 정의를 사용해 문제를 푸는 것이다.

 

나 같은 경우는 문제에서 원하는 바 대로, 파스칼의 삼각형을 이용하여 DP문제로 풀었다.

 

nCm = n-1Cm + n-1Cm-1의 점화식을 사용하여 구현하였다.

 

아마 큰 수 연산 지원이 되지 않는 다른 언어들 같은 경우는 큰 수 연산 중 덧셈만 구현한다면, 위의 점화식을 사용해 문제를 풀 수 있을 것이라고 생각한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2407번 조합
# 수학, 정수론, DP
DP = [1,5,10,10,5,1]
n, m = map(int, input().split())
for _ in range(n-5):
    new_dp = [1]
    for i in range(len(DP)-1):
        new_dp.append(DP[i]+DP[i+1])
    new_dp.append(1)
    DP = new_dp
print(DP[m])