[백준] 2407 조합 python

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

2407번: 조합

파이썬으로는 int나 long long등 변수 값의 최대 크기를 생각하지 않아도 되기 때문에 상당히 쉬운 문제이다.

일차원 변수를 사용해서 nCm = n! / ( (n-m)! * m! ) 으로 구현했다.

def main():
    n, m = map(int, input().split())
    fact = [1 for _ in range(n + 1)]
    for i in range(2, n + 1):
        fact[i] = fact[i - 1] * i
    print(fact[n] // fact[n-m] // fact[m])


if __name__ == '__main__':
    main()

 

하지만 C, C++로 풀때는 이야기가 달라진다. 이 문제에서 나올수 있는 최대 값은 100 C 50 = 100891344545564193334812497256 이다. 이 값은 long long size보다 더 큰 값이므로 쉽게 계산하지 못한다.

이를 풀기 위해선 gcc에서는 __uint128_t이라는 unsigned 정수 자료형을 제공하므로 이를 사용해서 쉽게 풀던지, string 자료형으로 바꿔서 풀면된다.

---

참고한 글

https://www.acmicpc.net/board/view/72957

글 읽기 - 2407) C++로 푸실려는 분들을 위한 글

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-2407%EB%B2%88-%EC%A1%B0%ED%95%A9-CC

[백준] 2407번 : 조합 [C/C++]