[Baekjoon] 1010번: 다리 놓기

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

1010번: 다리 놓기

 

수학적인 배경 지식을 어느정도 요구하는 문제였던 것 같다. 고등학생 때 경우의 수를 구하는 문제를 정말 극도로 싫어했었는데 문제를 해결하다보니 그 때의 생각이 물씬 났다. ㅎㅎ;;

 

이번 문제를 해결하는 것 자체는 사실 수리논리적으로 그렇게 어려운 일은 아니지만(반박 시, 당신의 말이 옳습니다) 초보 프로그래머로서는 프로그래밍적으로는 생각해 볼 여지가 꽤 많은, 좋은 문제라고 생각한다.

 

---

 

문제 해결 과정

착안

문제에서 주어진 핵심 조건:

 

• 서쪽의 사이트 개수만큼 (\(N\)개) 다리를 짓는다.
• 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.
• 다리끼리는 서로 겹쳐질 수 없다.

 

위의 세 가지 조건에 의해 구하는 경우의 수는 \(M\)개의 다리 중에서 순서를 고려하지 않고 \(N\)개의 다리를 뽑는 것과 같은 \(_{M}C_{N} =\) \(M \choose N\) 임을 확인할 수 있다(다리끼리 서로 겹쳐질 수 없다는 조건 때문에 동쪽의 \(M\)개의 다리 중에서 \(N\)개를 뽑고나면 서쪽의 \(N\)개의 사이트와 연결하는 방법은 항상 1 가지 밖에 존재할 수 없기 때문이다. 만약 다리끼리 서로 겹쳐질 수 있다는 조건일 경우, 구하는 경우의 수는 다리를 선택하는 순서가 유효하므로 \(_{M}P_{N} = M! / N!\)이 된다).

 

구현

일반적으로 조합(combination, 조합의 수는 이항계수(binomial coefficient) 라고도 한다)의 계산은 증가 속도가 매우 빠른 함수인 팩토리얼(=계승, factorial)의 계산을 포함하기 때문에 단순하게 계산하려고 하면 정수 오버플로(integer overflow)가 발생하여 오류가 발생하기 쉽다. 조합의 수를 계산할 때에는 아래와 같은 2 가지(이외의 방법이 있을 수도 있는지는 모르겠음) 방법을 생각해볼 수 있는 것 같다.

 

• 분자-분모의 pairing을 통한 계산(그냥 방금 지어낸 이름임, 일반적으로 뭐라고 표현하는지는 모름).

분자와 분모를 각각 팩토리얼 계산하고 마지막에 나눈다면 정수 오버플로가 발생하기 쉬우므로, 분자와 분모를 한번씩 곱하고 나누는 식으로 계산한다.

 

* 주의점: 정수형 데이터의 나눗셈에서는 일반적인 나눗셈이 아닌 몫 연산이 수행되어 나머지를 버리므로, 반복문에서 분모를 연산하는 순서에 따라 중간 연산 결과가 정수로 나누어 떨어질 수도, 그렇지 않을 수도 있다는 점이다.

- 분모를 나누는 순서가 \(N, N-1, ..., 1\)이 되도록 반복문을 구성하면 중간 연산 과정에서 정수로 나누어 떨어지지 않는 경우가 발생할 수 있어서 중간 연산을 double형을 사용해서 계산하고, 부동소수점 수의 오차 발생 소지 때문에 최종 계산 결과를 반올림한 다음 정수형 자료형으로 변환(cmath 헤더의 round 함수 이용)해야 한다.

- 분모를 나누는 순서가 \(1, 2, ..., N\)이 되도록 반복문을 구성하면 순차적으로 계산할 때 항상 중간 계산 결과가 정수로 나누어 떨어지므로 부동소수점 수로 굳이 계산하지 않고 정수형 자료형만으로 계산해도 된다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

int main()
{
	// 분자/분모 pairing을 통한 팩토리얼 계산
	int T, N, M;
	unsigned long long prod;
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%d %d", &N, &M);
	
		if (M - N < N)
			N = M - N;

		prod = 1;
		for (int j = 0; j < N; j++)
		{
			prod *= M - j;
			prod /= j + 1;
		}

		printf("%lld\n", prod);
	}
}

 

---

 

• 동적계획법을 이용한 계산

사실 이 방법은 정수 오버플로를 피하는 직접적인 방법은 아니고, 조합의 수를 빠르게 계산하는 방법이다(어차피 조합의 수 자체가 너무 커지면 기본 자료형을 이용할 때의 정수 오버플로는 피할 수 없음).

 

조합의 수는 특이한 성질을 가지고 있는데, 다음과 같은 점화식의 형태로 표현할 수 있다는 것이다. $$ _{M}C_{N} = _{M-1}C_{N-1} + _{M-1}C_{N} $$

이를 이용하여 동적계획법의 정의에 따라 메모이제이션(memoization)을 이용해 이미 계산한 값은 저장하여 나중에 같은 계산을 다시 수행하지 않고 가져와 사용하는 방식으로 조합의 수를 계산할 수 있다 (참고로 임의의 자연수 M에 대하여 \(_{M}C_{0} = 1\) 이다).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

unsigned long long Combination(int n, int r, unsigned long long save[][31])
{
	if (r == 0 || r == n)
	{
		save[n][r] = 1;
		save[n][n - r] = 1;
		return 1;
	}

	if (save[n][r] > 0)
		return save[n][r];
	else
	{
		save[n][r] = Combination(n - 1, r - 1, save) + Combination(n - 1, r, save);

		if (n != n - r && !save[n][n - r])
			save[n][n - r] = save[n][r];

		return save[n][r];
	}
}

int main()
{
	int T, N, M;
	scanf("%d", &T);

	unsigned long long Combination_Save[31][31] = { 0 };

	for (int i = 0; i < T; i++)
	{
		scanf("%d %d", &N, &M);

		if (M - N < N)
			N = M - N;

		printf("%lld\n", Combination(M, N, Combination_Save));
	}

	return 0;
}

 

실행 결과

위는 동적계획법을 이용한 계산 결과, 아래는 분모-분자 pairing을 통한 계산 결과임.

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

실행 결과로는 둘 다 0 ms로 측정이 되었으나, 이는 팩토리얼의 계산 자체가 숫자가 조금만 커져도 기본 자료형으로는 표현되지 않아 어쩔 수 없이 문제 자체가 많은 연산을 수행하지 않도록 설계되었기 때문인 것 같다. 일반적으로 보았을 때는 동적계획법을 이용하는 것이 프로그래밍 적으로 유리할 것 같다는 생각이 든다.