[C] 백준 1010번 다리놓기

1. 문제이해

1010번: 다리 놓기 (acmicpc.net)

1010번: 다리 놓기

 

문제를 요약하자면, 서쪽의 사이트의 개수(N)보다 동쪽의 사이트의 개수(M)가 같거나 많아야 하며,

서쪽의 사이트의 개수만큼 겹치지 않도록 서쪽과 동쪽의 다리를 이어야한다.

각 테스트 케이스와 N,M을 입력받아, 그에 대한 경우의 수를 출력하는 알고리즘을 만드는 것이 목표이다.

 

 

 

2. 문제풀이

 

예를 들어, 서쪽의 사이트의 개수(N)가 1, 동쪽의 사이트의 개수(M)가 5라고 해보자.

서쪽에서 동쪽까지 이을 수 있는 다리의 개수는 딱 5가지이다.

서쪽에 있는 하나의 다리에서 선택할 수 있는 동쪽의 다리의 개수가 5개이기 때문이다.

 

다른 예를 들어보자. 서쪽의 사이트의 개수(N)가 2, 동쪽의 사이트의 개수(M)가 5라고 해보자.

서쪽에서의 사이트의 개수가 2개이므로, 이제 다리를 겹치지 않게 놓아야 된다는 조건을 생각해야한다.

우선, 서쪽에서의 사이트의 개수만큼 동쪽의 사이트의 개수를 선택해보자.

M개 중에서 N개 만큼 선택 하는 것이므로, 다음과 같은 조합 공식을 이용하면 된다.

(조합 공식의 n자리에 M, r자리에 N을 대입하면 된다.)

 

조합 공식

 

그럼 이제 다리를 겹치지 않게 놓아야 된다는 조건을 생각해야 하는데, 사실 그럴필요가 없다.

겹치지 않을 경우는, N의 맨 위의 사이트와 선택된 M의 맨 위의 사이트끼리 짝을 짓고,

하나씩 차례대로 내려오며 짝을 짓는 경우밖에 없다.

 

즉, M개 중에서 N개 만큼 선택하기만 하면, 겹치지 않게 놓아야 된다는 것은 고려할 필요가 없다.

선택을 한 순간부터 이미 자동으로 배치가 된다는 것이다.

 

 

 

3. 소스코드

 

1. 첫번째 시도 (실패)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 30

int bridge(N, M) {
	int result = 0;	

	int facM = factorial(M);		// M!
	int facN = factorial(N);		// N!
	int facMN = factorial(M - N);	// (M-N)!

	result = (facM / (facN * facMN));

	return result;

}


int factorial(int n)
{

	if (n == 0)
		return 1;

	if (n == 1)      
		return 1;    // n이 1이 되면, 1을 반환하고 재귀호출을 끝냄

	return n * factorial(n - 1);    // 재귀호출
}


int main() {

	int N[MAX], M[MAX];	// N은 서쪽의 다리의 갯수, M은 동쪽의 다리의 갯수
	int testcase;		// 입력받을 테스트 케이스의 갯수
	int i = 0;			// 테스트 케이스만큼 반복하기 위한 변수
	int j = 0;

	scanf("%d", &testcase);
	for (i; i < testcase; i++) {
		scanf("%d %d", &N[i], &M[i]);	// 테스트 케이스만큼 N,M 받기
	}

	for (j; j < testcase; j++) {
		printf("%d\n", bridge(N[j], M[j]));
	}

	return 0;
}

위와 같이 코드를 작성해보니, 예시의 (1,5), (2,2)의 결과는 잘 출력되지만,

마지막 예시인 (13,29)를 출력 시, 0이 출력되는 문제가 발생했다.

이는 위의 예시를 계산하면 스택 오버플로우가 나기 때문인데,

이를 수정하기 위해 다음과 같은 점화식을 사용해주고

(점화식 사용을 편히 하기위해 이차원 배열로 수정해주었다.)

int형을 long long형으로 수정해주었다.

 

조합 점화식

 

2. 두번째 시도 (성공)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 30

long long int bridge(M, N) {
	static long long int NM[MAX][MAX];	// 내부 값 0으로 초기화

	if (NM[M][N] >0)
		return NM[M][N];	

	// 예외 처리 
	if (M == 0||N == 0) {
		return NM[M][N] = 1;
	}
	else if(N == M) {
		return NM[M][N] = 1;
	}

	return NM[M][N] = bridge(M - 1, N - 1) + bridge(M - 1, N);

}

int main() {
	int N, M;		// N은 서쪽의 다리의 갯수, M은 동쪽의 다리의 갯수
	int testcase;		// 입력받을 테스트 케이스의 갯수
	int i = 0;		// 테스트 케이스만큼 반복하기 위한 변수


	scanf("%d", &testcase);

	for (i; i < testcase; i++) {
		scanf("%d %d", &N, &M);	// 테스트 케이스만큼 N,M 받기
		printf("%lld\n", bridge(M, N));
	}


	return 0;
}

사실 두 번째 시도라고 하기에는 상당히 많은 시행착오를 겪었지만..

계속 런타임 에러나 시간초과같은 오류가 나서 한참 끙끙댔다..😥

위와 같이 N,M 값에 큰 값이 들어가면 오버플로우가 발생하는것과

예외 처리를 제대로 해주지 않은 것이 문제였다.

(M이 0일 경우에만 예외처리를 해주고, N이 0일 경우는 고려해 주지 않았었다..)

 

두번째 시도를 통해 만들어낸 코드에서는 큰 값이 들어갔을때의 오버플로우를 방지하기 위해

이차원 배열과 위의 조합 점화식, 그리고 long long int 형식을 사용해주었다.

사실 long long int 형식은 처음들어봤는데, double 처럼 큰 값을 출력해줄때 사용하는 변수라고 한다.

아직 배울것이 많이 남은 것 같다..

bridge 라는 함수를 따로 두어, 재귀호출을 통해 경우의 수를 계산하도록 구현했으며,

NM이라는 이차원 배열을 따로 두어 계산했다.

 

 

---

사실 조합을 이용하는 알고리즘이라는것을 이해한 후에는,

코드를  쉽게 짤 수 있을것이라고 생각했는데,

여러모로 변수나 생각할것이 많은 문제였던것같다.

아직 배울게 산더미같이 남았다는게 느껴진다..😰