문제
서쪽에 N개의 사이트 동쪽에 M개의 사이트가 있는데 한개씩 연결하여 다리를 만들 수 있는 경우의 수를 구하려고 한다. 그런데 이 때, 다리는 서로 겹치면 안되고 서쪽 사이트 개수만큼 만들려고 한다. T(테스트 케이스),N(서쪽 사이트), M(동쪽 사이트)가 주어진다. ( 0 < N ≤ M < 30)
접근
예제에서 발견할 수 있는 특징이 몇 개 있다.
각 순서쌍은 (서쪽 사이트, 동쪽 사이트)를 나타낸다.
1.
n == m 인 경우. 즉, (n, n)인 경우는 무조건 1 이다.
2.
(1, m) 인 경우 m개다.
3.
그 외
만약 (3,4)인 경우를 생각해 보면.
각 맨 위에 하나를 연결하고 나면 (2,3)이 된다.
지금 그럼 작게 쪼개진 것을 발견할 수 있다. 또 맨 위를 연결한다고 생각하면
(1,2)가 된다.
만약 서쪽의 첫번째와 동쪽의 두번째를 연결하면 개수가 같아지기 때문에 1번에 해당하게 된다. (즉, 1)
정리
(n,m) = (n-1, m-1) + (n-1, m-2) + ... + (n-1, n-1)(=1)
메모리 / 시간
1120 KB / 0 ms
코드
#include <stdio.h>
int M[30][30];
int re(int n, int m)
{
if(M[n][m]) return M[n][m];//이게 없어서 시간초과
if (n == 1) return m;
if (n == m) return 1;
int sum = 0;
for (int i = n - 1; i < m; i++)
sum += re(n - 1, i);
M[n][m] = sum;
return sum;
}
int main()
{
int tc, n, m;
scanf("%d ", &tc);
while (tc--)
{
scanf("%d %d", &n, &m);
printf("%d\n", re(n, m));
}
}
C
복사
