2/4 [C] 백준 1010번 - 다리 놓기

<문제>

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

1010번: 다리 놓기

 

<내가 제출한 답>

 

1. 첫번째 -----> 결과는 시간초과

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int combi(int m, int n) {

	if (n == m) return 1;
	if (n == 1) return m;
	return combi(m - 1, n - 1) + combi(m - 1, n); 
}

int main() {
	int testcase, n, m;

	scanf("%d", &testcase);

	while (testcase--) {
		scanf("%d %d", &n, &m);
		printf("%d\n", combi(m, n));
	}
}

(쉽지만 오래걸리는) 재귀함수때문에 시간초과인 결과가 나온듯

반복문으로 고쳐서 다시 제출해 보았다.

 

 

2. 두번째 -----> 틀렸습니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int combi(int m, int n) {
	long long i=1, j=1,test=n;

	if (m == n) return 1;
	if (n == 1) return m;

	while (test--) {
		i *= m;
		j *= n;
		m--;
		n--;
	}
	return i / j;
}

int main() {
	int testcase, n, m;

	scanf("%d", &testcase);

	while (testcase--) {
		scanf("%d %d", &n, &m);
		printf("%d\n", combi(m, n));
	}
}

이거 솔직히 세번째랑 다른게 없는데?? 틀렸다

백준에 나와있는 예시문제들은 다 잘 돌아간다..??

왜 틀렸을까

 

+) combi 처음에 n==0일때는 return 1; 추가해도 틀렸다고 나옴

 

3. 세번째 ----->맞았습니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int testcase, n, m, i;
	long long ans;

	scanf("%d", &testcase);

	while (testcase--) {
		ans = 1;
		scanf("%d %d", &n, &m);
		for (i = 1; i <= n; i++) {
			ans *= m;
			ans /= i;
			m--;
		}

		printf("%d\n", ans);
	}
}

그냥 계속 틀리길래 그냥 main에 다 썼다

이건 맞음