[백준 2407 C++] 조합

조합 문제 링크 (백준(BOJ) 2407번 문제): https://www.acmicpc.net/problem/2407

2407번: 조합

문제 풀이

백준 2407번 조합 문제는 Combination 값을 구해서 출력하는 단순한 문제다. 파이썬을 사용한다면, 이 문제에 테스트 케이스로는 Integer Overflow가 발생하지 않아 쉽게 풀 수 있다. 하지만, C++을 사용한다면 Combination(100,50)의 경우 값이 10^29승 정도 되는 값이 나오게 되어 Integer Overflow가 발생한다. 

 

그리하여, C++에서 이를 구현하기 위해선 __uint128_t 타입을 사용하면 위와 같은 케이스의 결과 값을 들고 있을 수 있게 된다. 하지만 결과를 바로 출력할 수 없으므로 문자열 형태로 바꿔서 출력해주어야 한다. 

 

그리하여, 가장 큰 값이  10^29승 정도의 값이므로 몫과 나머지 연산을 통해 문자열로 바꿔주면 풀 수 있다. 

이를 코드로 구현하면 아래와 같다.