[백준 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승 정도의 값이므로 몫과 나머지 연산을 통해 문자열로 바꿔주면 풀 수 있다. 

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

 

	#include <iostream>
	#include <cmath>
	#define MAX 101
	using namespace std ;
	int N, M;
	__uint128_t C[MAX][MAX] ;
	__uint128_t Combination(int n, int m) {
	if ( C[n][m] > 0 ) return C[n][m] ;
	if ( m == 1 ) return n ;
	if ( n == m || m == 0 ) return 1 ;
	if ( m > n/2 ) {
	m = n - m ;
	}
	return C[n][m] = Combination(n -1, m - 1) + Combination(n - 1, m) ;
	}
	void Input() {
	cin >> N >> M ;
	}
	int main(void) {
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	Input() ;
	C[1][1] = C[1][2] = 1 ; C[2][1] = 2 ;
	__uint128_t result = Combination(N,M) ;
	string r = "";
	string f = to_string((long long) (result / (__uint128_t) pow(10, 15))) ;
	string s = to_string((long long) (result % (__uint128_t) pow(10, 15))) ;
	if ( f == "0") {
	r = s ;
	} else {
	r = f + s;
	}
	cout << r << '\n';
	return 0 ;
	}

view raw 2407.cpp hosted with ❤ by GitHub