[백준 / C언어] 1010번: 다리 놓기

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

1010번: 다리 놓기

 

난이도: solved.ac 실버 5

 

 

사용 알고리즘

---

조합

 

 

접근 방법

---

조합을 활용한 문제다

 

다리를 놓는다는 것은 강 동쪽의 사이트 M개에서 강 서쪽의 사이트 N개로 선을 잇는다는 것인데,

 

이는 곧 M개에서 N개를 선택하는 경우를 말한다

 

경우의 수를 구하는 문제이므로 순열 또는 조합을 이용해야 할 텐데

 

여기서 순열이 아니고 조합인 이유는 바로

 

강 동쪽의 사이트에서 강 서쪽의 사이트로 다리를 놓는데 다리끼리는 서로 겹칠 수 없기 때문이다

 

 

 

구현

---

이전의 11051번 이항계수 2에서 사용했던 코드와 거의 똑같다

(코드 이해가 안되시는 분은 위의 링크를 타고 들어가 참고해 보세요)

 

11050번 이항계수 1에서 풀었던 대로 Combination을 직접 계산해도 정답처리가 되지만, dp 복습을 할 겸 dp를 이용해 풀었다

 

여러 번의 테스트 케이스만큼 출력을 하는데 매번 dp를 계산하기 번거로우므로

 

dp[30][30]까지 미리 만들어둔 후에 입력이 들어올 때마다 해당 위치의 dp[M][N]를 출력하는 식으로 만들었다

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int dp[31][31];

int main() {
	int N, M, i, j;
	for (i = 1; i <= 30; i++) {
		dp[i][0] = 1;
		dp[i][i] = 1;
		dp[i][1] = i;
	}
	for (i = 3; i <= 30; i++)
		for (j = 2; j <= i; j++)
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

	int test_case, T;
	scanf("%d", &T);
	for (test_case = 1; test_case <= T; test_case++) {
		scanf("%d %d", &N, &M);
		printf("%d\n", dp[M][N]);
	}
	return 0;
}