2407번 - 조합

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

2407번: 조합

C++로 처음에 풀었었는데, 잘 작동을 하는 것 같았다. 하지만 결과는 "틀렸습니다".. 질문을 검색하다 보니..

C(100 , 50)인 100891344545564193334812497256로 약 10^29 정도의 수인데, 이 수를 제대로 출력을 못해주고 있었다. C++로 해결하는 방법은 gcc에서 제공해주는 __uint128_t이라는 unsigned 정수 자료형을 사용해야 한다.

 

잘 모르겠어서, 파이썬으로 풀었다. C++로 해결하는 방법은 참고한 링크를 첨부하겠다.

https://ethical-hack.tistory.com/64

[백준 2407 C++] 조합

dp = [[0 for col in range(101)] for row in range(101)]
N, M = map(int, input().split())
def solve(N, M):
    for i in range(0, N+1):
        dp[i][0] = 1;
    for i in range(1, M+1):
        dp[i][i] = 1;
    for i in range(2, N+1):
        for j in range(1, M+1):
            if i<j:
                continue
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
    return dp[N][M]
print(solve(N, M))