[백준알고리즘] 2407번: 조합 -C++

[백준알고리즘] 2407번: 조합 -C++

2407번: 조합 (acmicpc.net)

2407번: 조합

이번 문제는 다른 분의 코드를 참고해서 풀었다.

- 참고 : [백준] 2407번 조합 - C++ - DGOS | 동꿀오소리 (donggoolosori.github.io) 

 

문제를 보고, unsigned long long 이라도 연산 범위를 벗어날 것이라는 것은 알았다. 대충 \(100!/50!/50!\) 해봐도 결괏값이 어마어마하게 컸다. 하지만, 여기서 '문자열'로 큰 수 처리를 하는 것을 기억하지 못했다.

그래서 다른 분들의 코드를 참고했다. 아직 예전만큼 코테를 자연스럽게하려면 많이 남았다.

 

그래도 점화식은 쉽게 구했다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

조합에 대한 점화식은 가물가물했다. 그래서 몇가지에 대해 일일이 작성해서 직접 점화식을 찾았다.

nCm 조합의 값

 

위의 그림을 보면서 몇가지 특징을 발견할 수 있었고, 계산 방법(점화식)을 찾아냈었다.

• \(_{n} C_{m} = _{n-1} C_{m} + _{n-1} C_{m-1}\)

 

위 점화식을 정리한 것이 파스칼 삼각형이다.

- 참고 : 파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

여기에, DP를 위한 Memorization을 사용했고, 큰 수의 연산을 위해 문자열을 사용했다.

 

큰 수의 연산에서는 두 문자열의 가장 마지막 자리부터 int로 변환해 정수 연산처럼 해나가는 방식을 사용했다. C++11부터는 문자열(string) 연산 시에 back(), pop_back()과 같은 것들을 사용하면 쉽게 처리할 수 있다.

나는 C++98에서도 통과 가능하도록 조금 꼬아서 'end() - 1'로 back()을 대체했고, pop_back()은 erase()로 대체 사용했다.

 

#include <cstdio>
#include <string>
#include <algorithm>

const unsigned int MAX_SIZE = 100 + 1;

std::string arrCombi[MAX_SIZE][MAX_SIZE] = { "", };

std::string sumString(std::string sFirst, std::string sSecond) {
	std::string sRet;
	int iSum = 0; // 위의 자리수에 더할 값

	while ( false == sFirst.empty() || false == sSecond.empty() || 0 < iSum ) {
		std::string::iterator itLast;

		if ( false == sFirst.empty() ) {
			itLast = sFirst.end() - 1;
			iSum += (*(itLast) - '0');
			sFirst.erase(itLast);
		}
		if ( false == sSecond.empty() ) {
			itLast = sSecond.end() - 1;
			iSum += (*(itLast) - '0');
			sSecond.erase(itLast);
		}

		// 현재 자리의 값
		sRet.push_back((iSum % 10) + '0');
        // 올림수
		iSum /= 10;
	}

	std::reverse(sRet.begin(), sRet.end());
	return sRet;
}

std::string combination(int n, int m) {
	if ( m == n || 0 == m ) {
		return "1";
	}

	std::string &sRet = arrCombi[n][m];
	if ( false == sRet.empty() ) {
		return sRet;
	}

	sRet = sumString(combination(n - 1, m), combination(n - 1, m - 1));
	return sRet;
}

int main(void) {
	/* 입력 */
	int N, M;
	scanf("%d %d", &N, &M);

	/* 출력 */
	printf("%s", combination(N, M).c_str());

	return 0;
}