✔ 풀이를 위한 아이디어
- 다이나믹 프로그래밍 (Dynamic Programming)
- 조합론 [ n_C_r = n-1_C_r-1 + n-1_C_r ]
- 임의 정밀도 / 큰 수 연산 => Python에서는 상관 X
✔ 정답 코드
import sys
n, m = map(int, sys.stdin.readline().split())
dp = [[-1]*(m+1) for _ in range(n+1)]
def recurComb(x, y):
if dp[x][y] != -1: # 수가 커질 수록 다시 방문할 확률이 높아지므로 필수!
return
if y == 1:
dp[x][y] = x
return
if x == y:
dp[x][y] = 1
return
recurComb(x-1, y)
recurComb(x-1, y-1)
dp[x][y] = dp[x-1][y] + dp[x-1][y-1]
recurComb(n, m)
print(dp[n][m])- 우선, 조합을 DP로 풀어야한다는 점에서 [ n_C_r = n-1_C_r-1 + n-1_C_r ] 의 공식을 써야한다는 점을 쉽게 눈치챌 수 있었다.
- 쉬운 난이도의 DP 문제는 숫자가 작은 것부터 계산해나가지만, 이 경우에는 큰 것부터 쪼개나가야 하므로 재귀를 활용하기로 결정하였다.
- 계속해서 함수를 재귀호출 해나가다가, n_C_r에서 r이 1이 됐을 때 n과 r이 같아졌을 때 (조합의 값을 연산 없이 구할 수 있는 경우) 2차원 배열에 값을 넣어주고 return한다.
- 여기까지 했을 때 수가 작은 경우는 잘 구해내지만, 수가 커질 경우 시간이 지나치게 오래 걸리게 되는 문제점을 발견하였다.
- print문을 활용해 확인해보니, 이미 방문했던 (값이 -1이 아닌) 곳을 계속해서 방문하고 있었고, 첫번째 if문을 추가해줌으로써 해결되었다.
Web 공부를 하느라 약 한달 간 PS를 쉬었는데, 오늘부터 다시 시작하려고 한다! 얼른 감 되찾자!
✔ 추가로 공부해볼 것들
- 파이썬에서 정수의 크기에 제약이 없는 이유, 임의 정밀도: https://mingrammer.com/translation-cpython-internals-arbitrary-precision-integer-implementation/
