백준 1010번

백준 1010번은 고등학교 때 배운 조합(Combination)을 이용하는 문제이다. 문제 자체에서도 조합을 이용한다고 나와 있었기 때문에, 의외로 쉽게 조합을 이용한다는 것을 파악할 수 있었다. 문제는 코딩 단계에서 일어났다.

#include <stdio.h>

int combination(int, int);

int main(void) {
	int num;
	scanf("%d", &num);
	long long result;
	int n, m;
	for (int i = 0; i < num; i++) {
		scanf("%d %d", &n, &m);
		result = combination(m, n);
		printf("%d\n", result);
	}
}
int combination(int n, int k) {
	if (n == k) {
		return 1;
	}
	else if (k == 1) {
		return n;
	}
	else {
		return combination(n - 1, k - 1) + combination(n - 1, k);
	}
}

처음 올렸었던 코드이다. 기본적인 조합의 점화식을 이용, 재귀함수를 만들어서 직접 계산하는 코드이다. 하지만, 재귀함수를 사용하면 꼭 시간 초과가 나왔다. 이 전에 작성한 코드는 팩토리얼을 이용해서 직접 계산한 후, 나누기를 하는 코드였지만 나눗셈은 c언어에서 실수형으로 계산해야 나오기 때문에 답이 제대로 나오지 않았다.

우리가 기본적으로 계산을 할 때는 분모와 분자를 따로 계산한 후, 나눗셈을 진행한다. 하지만, 프로그래밍 언어로 이를 구현할 때는 제약이 많아진다. 기본적으로 이 코드를 짤 때 제약은 바로 변수형이었다. 그래서, 곱셈을 하면서 나눗셈도 함께 할 수 있는 방법을 찾아서 코드를 구현해 보았다.

#include <stdio.h>

int main(void) {
	int num;
	scanf("%d", &num);
	long long result = 1;
	for (int i = 0; i < num; i++) {
		int n, m;
		scanf("%d %d", &n, &m);
		for (int j = 0; j < n; j++) {
			result = result * (m - j);
			result = result / (1 + j);
		}
		printf("%d\n", result);
		result = 1;
	}
}

재귀함수는 최대한 쓰지 않고, 다른 논리를 이용해서 푸는 것이 중요하다고 느낀 문제였다.