[백준][C#] 2407 조합 - 실버3

문제 보기

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

2407번: 조합

 

 

문제

nCm을 출력한다.

 

 

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

 

 

출력

nCm을 출력한다.

 

 

얼핏 보아서는 간단해보이는 문제이다.

처음 봤을 때는 왜 실버에 이런 문제가 있지 생각하였지만

풀다보면 이유를 알 수 있는 문제.

 

조합에 대한 자세한 설명은 아래 블로그를 참고하면 된다.

https://mathbang.net/547#gsc.tab=0

순열과 조합 - 조합이란

 

조합 nCm이 주어지면

보통 n! / (n-m)! * m! 이라는 수식을 사용한다.

만약 n의 최대값인 500이 들어온다면?

n!는 122013682599111006870123878542304692625357434280319284219241358838584537315388199760549644750220328186301361647714820358416337872207817720048078520515932928547790757193933060377296085908627042917454788242491272634430567017327076946106280231045264421887878946575477714986349436778103764427403382736539747138647787849543848959553753799042324106127132698432774571554630997720278101456108118837370953101635632443298702956389662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535905669342381300885624924689156412677565448188650659384795177536089400574523894033579847636394490531306232374906644504882466507594673586207463792518420045936969298102226397195259719094521782333175693458150855233282076282002340262690789834245171200620771464097945611612762914595123722991334016955236385094288559201872743379517301458635757082835578015873543276888868012039988238470215146760544540766353598417443048012893831
3896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

라는 터무니 없는 큰 숫자를 만들어버리고 만다.

이런 숫자는 long으로도 해결 불가능하다.

 

그럼 어떻게 해야 하는가?

두 가지 방법이 있다.

첫 번째는 큰 수를 담을 수 있는 Biginteger를 사용하는 것

두 번째는 string에 수를 담는 것이다.

나는 두 번째 방법을 사용하였다.

 

string에 값을 저장하고 자릿수별로 더해가면서 계산을 진행하였다.

이 방식을 사용하기 위해서는 우선, 조합을 구하는 또 다른 방법을 사용해야 한다.

 

nCr = n-1Cr-1 + n-1Cr 이라는 공식을 이용하는 것인데

이는 파스칼의 삼각형 규칙이라 부른다.

 

파스칼의 삼각형에 대한 설명

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전

 

n개 중 r개를 뽑는 것은

어떤 수 i가 있다고 가정할 때

i를 뽑는 경우의 수 n-1Cr-1과 (i를 이미 뽑았기 때문에 i를 제외한 숫자 중, i를 제외했을 때의 갯수 만큼 뽑는 것)

i를 뽑지 않는 경우의 수 n-1Cr의(i를 제외한 숫자 중, r개 뽑는 것)의 합과 동일하다는 뜻.

 

private static string Combination(int n, int r)
{
	// temp는 string 배열. 불필요한 계산을 피하도록 메모이제이션
    if (temp[n, r] != null)
    	return temp[n, r];
    else
    {
    	// n개 중에 n개를 뽑는 조합, 0개를 뽑는 조합은 1개 
    	if (n == r || r == 0)
    		return "1";
		
        // 재귀 호출
    	temp[n, r] = AddString(Combination(n - 1, r - 1), Combination(n - 1, r));

    	return temp[n, r];
    }
}

 

 

그럼 이제 string을 사용하여 큰 수를 덧셈하는 방법을 알아보자.

 

원리는 간단하다.

string과 string의 1의 자릿수부터 더해주고,

그 값이 10 이상이라 다음 자릿수로 넘어가야 한다면,

sum(더한 값)을 10으로 나누어주고 다음 자릿수에서 더해주면 되는 것이다.

 

StringBuilder sb = new StringBuilder();
// a, b는 string을 거꾸로 뒤집은 것
int sum = 0;
// 모든 수를 다 더할 때까지
while (index < a.Length || index < b.Length || sum != 0)
{
    if(index < a.Length && index < b.Length)
    {
    	// - '0'으로 char를 int로 바꿔준다.
    	sum = sum + aArray[index] - '0' + bArray[index] - '0';
    }
    else if (index < a.Length)
    {
    	sum = sum + aArray[index] - '0';
    }
    else if(index < b.Length)
    {
    	sum = sum + bArray[index] - '0';
    }

	// StringBuilder에 추가 (1의 자릿수만)
    sb.Append(sum % 10);
    sum /= 10;

    index++;
}

 

 

 

 

전체 코드

internal class Program
    {
        static string[,] temp = new string[101,101];
        static void Main(string[] args)
        {
            using var reader = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            string input = reader.ReadLine();

            int n = int.Parse(input.Split()[0]);
            int m = int.Parse(input.Split()[1]);

            string result = Combination(n, m);
            print.WriteLine(result);
        }

        private static string Combination(int n, int r)
        {
            if (temp[n, r] != null)
                return temp[n, r];
            else
            {
                if (n == r || r == 0)
                    return "1";

                temp[n, r] = AddString(Combination(n - 1, r - 1), Combination(n - 1, r));
                
                return temp[n, r];
            }
        }

        private static string AddString(string a, string b)
        {
            StringBuilder sb = new StringBuilder();
            // string을 뒤집기 위해 char[]을 사용하였다.
            char[] aArray = a.ToCharArray();
            Array.Reverse(aArray);
            char[] bArray = b.ToCharArray();
            Array.Reverse(bArray);

            int index = 0;
            int sum = 0;
            
            while (index < a.Length || index < b.Length || sum != 0)
            {
                if(index < a.Length && index < b.Length)
                {
                    sum = sum + aArray[index] - '0' + bArray[index] - '0';
                }
                else if (index < a.Length)
                {
                    sum = sum + aArray[index] - '0';
                }
                else if(index < b.Length)
                {
                    sum = sum + bArray[index] - '0';
                }

                sb.Append(sum % 10);
                sum /= 10;

                index++;
            }
            char[] result = sb.ToString().ToCharArray();
            Array.Reverse(result);

            return string.Concat(result);
        }
    }