2407 조합

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

from fractions  import Fraction
n,m = map(int,input().split())

dp_table = [1 for _ in range(n+1)]

for i in range(2,n+1):
    dp_table[i] = dp_table[i-1]*i


print(Fraction(dp_table[n],(dp_table[n-m]*dp_table[m])))
# from math import factorial as f
# print(Fraction(f(n),(f(n-m)*f(m))))

3. 풀이 및 생각

문제 풀이

이 문제의 핵심은 dp를 이용하는 것이라고 생각한다. 조합은 factorial들을 3번 구해야한다. 이게 값이 작으면 모르겠지만.. 100단위를 넘어가게되면 100이상의 수를 3번이나 factorial하는 것은 100이 넘은 for문을 3번 이용하는 것이므로 할 순 있지만, 더 좋은 방법이 있다. 그게 바로 dp table을 이용하는 것. 왜냐하면 단순히 100이 넘는 for문을 1번만 이용해서 조합문제를 풀 수 있기 때문이다. 그래서 이 문제를 dp로 풀어야겠다고 생각했다.

그러나 여기서 중요한 점이 하나 있는데, 오늘 처음 알았다. 일반적인 / 기호는 값이 커질수록 그 값을 제대로 표현하지 못한다고 한다. 그래서 fractions 라이브러리의 Fraction()을 이용해서 나눗셈을 사용해야한다.

나의 생각

다음부턴 /의 표현을 쓰게되면 Fraction()을 이용하는 습관을 갖도록 하자.