import sys
import itertools
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
east = [i + 1 for i in range(M)]
result = list(itertools.combinations(east, N))
cnt = len(result)
print(cnt)
첫 시도이다.
이코테에서 부록에서 조합을 공부했는데 그것을 활용해서 풀기로 했다.
mCn의 갯수가 곧 정답이니 이것을 리스트에 담고 리스트의 길이를 구하는 방식이다.
정답은 맞지만 조금만 더 숫자가 커지기만 해도
프로그램이 죽어버린다. 보니 약 7000만 크기의 리스트를 선언하는 상황까지 도달해 프로그램이 종료되는 것이다.
그래서 고등학교 수학때 배운 조합 공식을 이용하기로 했다.
import sys
from math import factorial
input = sys.stdin.readline
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
result = factorial(M) // factorial(M - N) // factorial(N)
print(result)
공식으로 조합 값을 얻어내니 시간초과가 나지 않았고 해결되었다.
그런데 이건 다이나믹 프로그래밍 문제가 아닌가? 다른사람 문제풀이를 참고해보았다.
오 이렇게 바로 구해지는 방법도 있긴했다.