[C#] 1010번: 다리 놓기

목차

---

백준 단계별로 풀어보기

25.11.30

17단계: 조합론

1010번: 다리 놓기

문제 링크 : https://www.acmicpc.net/problem/1010

 

문제를 풀기 위해 알아야 할 개념

>> 조합의 개수

: 서로 다른 n 개에서 순서를 생각하지 않고 k 개를 선택하는 조합의 수는 아래 공식과 같다.

--> k = 0 이거나 n = k 라면 조합의 개수는 1개다.

출처 : https://velog.io/@baekgom/%EC%A1%B0%ED%95%A9-%EA%B3%B5%EC%8B%9D

 

>> 파스칼 삼각형과 조합

출처 : https://velog.io/@baekgom/%EC%A1%B0%ED%95%A9-%EA%B3%B5%EC%8B%9D

출처 : https://velog.io/@baekgom/%EC%A1%B0%ED%95%A9-%EA%B3%B5%EC%8B%9D

 

▶ 이를 조합 공식으로 나타내면 다음과 같다.

: 각각 '조합 공식 / 간단히 표현 / n과 r의 이항계수' 를 나타낸 것이다.

출처 : https://velog.io/@baekgom/%EC%A1%B0%ED%95%A9-%EA%B3%B5%EC%8B%9D

 

▶ 예시

: a b c 3개의 공 중에서 2개의 공을 뽑는 경우의 수는 'a를 선택할 경우' + 'a를 선택하지 않을 경우' 이다. 즉, a 외에 '나머지 2개 중 1개를 고를 경우' + '나머지 2개 중에서 2개 모두 고르는 경우' 이다.

--> 따라서 n 개의 공에서 r 개를 뽑는 경우의 수는 이미 하나를 뽑았다고 생각하고 n - 1 개의 공에서 r - 1 개를 뽑는 경우와 n - 1 개의 공에서 r 개를 뽑는 경우를 더한 것과 같다. (nCr = [n-1]C[r-1] + [n-1]Cr)

→ 이를 바탕으로 결국 더 이상 쪼개지지 않을 때까지, 즉 nC0 = 1이 될 때까지 재귀를 통해 구할 수 있다.

 

※ 참고 블로그

조합 공식 + 파스칼 삼각형

 

문제 풀이

>> 오답노트

: 재귀함수 형태로 조합의 개수를 구했더니 시간 초과로 실패했다.

 

- 작성한 코드

<hide/>
using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int t = int.Parse(sr.ReadLine());

        for (int i = 0; i < t; i++)
        {
            string[] input = sr.ReadLine().Split();
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);

            sb.AppendLine(Combination(m, n).ToString());
        }
        sw.Write(sb.ToString());
    }

    static long Combination(int n, int r)
    {
        if (n == r || r == 0)
            return 1;

        return Combination(n - 1, r - 1) + Combination(n - 1, r);
    }
}

 

>> 최종 수정

: 2차원 배열로 모든 값을 미리 계산해두고 입력값에 맞는 값을 출력하는 방식으로 변경하여 시간을 단축했다.

--> int의 범위를 초과하는 경우가 있으니 long 타입으로 만들어야 한다.

1. StreamReader로 입력값을 받아 int값으로 변환하여 테스트 케이스의 개수를 담을 변수 t 에 담는다.
2. long 타입의 2차원 배열 c 를 [30, 30]의 크기로 초기화한다. (0 < N ≤ M < 30 이기 때문)
3. 이중 for 반복문을 통해 모든 조합의 개수를 미리 구한다.
   •     nC0 = nCn = 1 로 값을 넣는다.
   •     for 반복문을 통해 파스칼 삼각형으로 조합의 개수를 구하여 값을 넣는다.
4. for 반복문을 통해 테스트 케이스 개수만큼 반복하여 StreamReader로 입력값을 받아 각각 int값으로 변환하여 서쪽과 동쪽에 있는 사이트의 개수를 담을 변수 n 과 m 에 담고, 미리 구한 해당 값의 조합의 개수를 StringBuilder에 담는다.
5. StreamWriter로 StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());
        StringBuilder sb = new StringBuilder();

        int t = int.Parse(sr.ReadLine());

        long[,] c = new long[30, 30];
        for (int i = 0; i < 30; i++)
        {
            c[i, 0] = c[i, i] = 1;
            for (int j = 1; j < i; j++)
            {
                c[i, j] = c[i - 1, j - 1] + c[i - 1, j];
            }
        }

        for (int i = 0; i < t; i++)
        {
            string[] input = sr.ReadLine().Split();
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);

            sb.AppendLine(c[m, n].ToString());
        }
        sw.Write(sb);
    }
}