C# [백준 BAEKJOON] 2407번 조합

목차

• 문제
• 입력
• 출력
• 풀이 코드
• Combination 함수에서 알수 있는 조합의 성질
• 메모화로 최적화 하기
• 참고하면 좋은 글

문제

nCm을 출력한다.

 

입력

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

 

출력

nCm을 출력한다.

 

2407번: 조합

 

 

풀이 코드

해당 문제를 풀이하기 위해선 큰 수 더하기, 조합, 메모이제이션을 익혀야 한다. 하나씩 익히면서 풀어보자.

 

using System;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        string[,] ss = new string[101, 101];

        var input = Console.ReadLine().Split();
        var num1 = Int32.Parse(input[0]);
        var num2 = Int32.Parse(input[1]);

        Console.WriteLine(Combination(ss, num1, num2));
    }

    static string BigNumerAdd(string num1, string num2)
    {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        var s = "";

        if (num1.Length <= num2.Length)
        {
            for (int i = 0; i < num2.Length - num1.Length; i++)
            {
                s += "0";
            }

            num1 = s + num1;
        }
        else
        {
            for (int i = 0; i < num1.Length - num2.Length; i++)
            {
                s += "0";
            }

            num2 = s + num2;
        }

        for (int i = num1.Length - 1; 0 <= i; i--)
        {
            var digit1 = num2[i] - '0';
            var digit2 = num1[i] - '0';
            var prevCarry = 0;

            if (carry > 0)
            {
                prevCarry++;
                carry = 0;
            }

            if (10 <= digit1 + digit2 + prevCarry)
            {
                carry++;
            }

            sb.Append((digit1 + digit2 + prevCarry) % 10);
        }

        if (carry > 0)
        {
            sb.Append(1);
        }

        return new string(sb.ToString().Reverse().ToArray());
    }

    static string Combination(string[,] ss, int n, int r)
    {
        if (ss[n, r] != null)
        {
            return ss[n, r];
        }
        else if (n == r || r == 0)
        {
            ss[n, r] = "1";
        }
        else
        {
            ss[n, r] = BigNumerAdd(Combination(ss, n - 1, r - 1), Combination(ss, n - 1, r));
        }

        return ss[n, r];
    }
}

 

Combination 함수에서 알수 있는 조합의 성질

조합의 성질에 대해서

메모화로 최적화 하기

C# 메모화(Memoization)

참고하면 좋은 글

[백준 BAEKJOON] 10757번 큰 수 A+B

[백준 BAEKJOON] 6603번 로또