백준 2407번 – 조합 (그리고 C로 직접 짜본 Big Integer)

백준 2407번 – 조합 (그리고 C로 직접 짜본 Big Integer)

백준의 2407번 조합문제(https://www.acmicpc.net/problem/2407)이다. 문제 자체는 매우 간단하다.  nCk를 출력하세요. 이다. n과 k는 100 이하이다.

너무 간단해서 그냥 메모이제이션 써야지~ 했다가 당연히 틀렸다. 출력예씨로 나온 100C6은 자료형 unsigned long long 범위 안에 들어가지만, 그렇지 않은 경우가 많다. 예를 들어 100C50같은 경우는

100891344545564193334812497256

가 되어버린다. 지나치게 길다.

 

대부분의 언어의 경우 이런 큰 수를 다룰 수 있는 BigInteger라는 자료형을 라이브러리 등으로 제공한다. 하지만 사내 코딩테스트를 준비하는 입장으로서, 사내 코딩테스트에서는 stdio.h 를 제외하고는 외부 라이브러리를 허용하지 않기 때문에.. 직접 만드는 수 밖에 없었다. 다음은 백준에서 통과한 코드이다.

 

 

기본적으로 메모이제이션 기법으로 푼다.  cache라는 공간에 메모이제이션으로 1C1부터 100C100까지 모든 수치를 다 구해놓고, 원하는  nCk를 바로 불러오는 형식이다.

이제 bigInteger를 만들어야한다. 나는 integer를 20개를 이어붙인 자료구조를 상상했다. 그래서 기본적으로 한 숫지는 int bigInteger[20]이다. bigInteger[0]이 제일 낮은 자리 5자리를 표시한다. 그 다음 5자리 숫자는 bigInteger[1]에 들어가고.. 이런 식이다. 이런 숫자를 N*K개만큼 만들었다.

여기서 사용되는 연산은 덧셈밖에 없어서 덧셈만 만들었다. addTo(from, to)는 from에 있는 숫자를  to에 더해준다. 가장 밑자리 수 5자리부터 차례로 더하면서 남는 부분은 다음 자리 수로 올려서 더해주는 식이다.

마지막으로 printBigInteger()가 있다. 숫자는 가장 높은 자리수부터 표기하기 때문에, 지금까지와는 다르게 bigInteger[20]부터 출력을 해줘야한다. 이 부분이 구현이 좀 까다로웠다. 가장 높은 자리 수가 나오기 전 까진 출력하지 않다가, 가장 높은 자릿수가 발견되면 그 부분은 일단 바로 출력, 그리고 그 이후에는 % 연산을 이용해서 0까지 제대로 출력해주어야 한다. 그렇지 않으면 다음과 같은 일이 발생한다.

200000를 표현하고 싶을 때

bigInteger[1] = 2

bigInteger[0] = 00000

-> 그냥 bigInteger[1] , bigIntger[0]순서대로 출력하면 :

printBigInteger(bigInteger) = 20

 

지금은 덧셈만 구현해봤지만, 기회가 되면 나머지 연산에 대해서도 구현을 해봐야 할 것 같다. 그리고 메모이제이션을 하면서 정수 배열을 가리키는 함수가 많았는데, 이 부분도 더 자세히 공부해야겠다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다