백준 1010

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

실패한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int bridgeCnt(int N, int H) {
	if (N == 1) {
		return H;
	}
	if (N == H) {
		return 1;
	}
	while (N < H) {
		return bridgeCnt(N,--H) + bridgeCnt(N - 1, H);
	}
}

int main() {
	int T, N, M;
	scanf("%d", &T);
	for (int j = 0; j < T; j++) {
		scanf("%d %d", &N, &M);
		printf("%d\n", bridgeCnt(N, M));
	}
}

실버 5짜리 문제.. 2시간동안 머리 쥐어짜서 짰지만 시간초과가 뜬다.. 알고리즘은 2학년 2학기때 배우는디 나한텐 너무 이른가 싶다.. ㅠㅠ
구글링 해보니 간단한 문제더라.. ㅋㅋㅋ 재귀함수 써야 해결될 줄 알았는디 그냥 고딩때 배운 조합 문제였을 줄이야..

수정한 코드 :

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

그러나 틀렸다고 나온다.. ㅠㅠ 이것도 구글링 해보니까 for 돌려서 result 에 값 넣을때 long long int 의 범위를 초과하는 경우때문에 그렇다고 한다. 그래서 곱셈을 수행할 때 나눗셈도 같이 수행하기로 했다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

배운점 :
배울게 너무 많다.. 문제를 많이 풀어보자...!!!