1010번: 다리 놓기

Memo

• 다리를 놓는 경우가 중복이 되면 안된다는 점에서 조합을 떠올릴 수 있었습니다.

Code

제출 날짜

2021/03/08

메모리

2020 KB

시간

0 ms

#include <iostream>
#include <vector>
#define endl "\\n"

int T, N, M, ans;
std::vector<std::vector<int> >save;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> T;
	save.resize(30, std::vector<int>(30));
}

int combination(int y, int x)
{
	if (save[y][x] != 0)
		return (save[y][x]);
	if (x == y || x == 0)
		return (1);
	save[y][x] = combination(y - 1, x - 1) + combination(y - 1, x);
	return (save[y][x]);
}

void solve()
{
	int x, y;
	std::cin >> x >> y;
	if (save[y][x])
		ans = save[y][x];
	ans = combination(y, x);
}

void print_val()
{
	std::cout << ans << endl;
}

int main()
{
	input();
	while (T--)
	{
		ans = 0;
		solve();
		print_val();
	}
	return (0);
}