백준 1010번: 다리 놓기

[문제 링크]

1010번: 다리 놓기

---

이 문제는 점화식을 세우는 과정에서 자꾸 뇌정지가 와서 오래 걸린 문제였다.

 

top-down 방식의 경우 사이트가 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수는 서쪽의 N번째 사이트와 동쪽의 M번째 ~ N번째 사이트가 연결되는 경우의 수들의 합이다.

N = 2, M = 3일 때 연결될 수 있는 다리

기저사례로 서쪽 사이트가 1개일 때, 동쪽 사이트 개수를 반환하고, 서쪽 사이트와 동쪽 사이트 개수가 같다면 1을 반환하였다.

 

bottom-up 방식의 경우 서쪽에 N개 동쪽에 M개 있을 때 다리를 짓는 경우의 수 = 서쪽의 N번째 사이트가 동쪽의 M번째 사이트와 연결되는 경우의 수 + 동쪽의 M-1번째 사이트와 연결되는 경우의 수이며, 이를 구현하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

int memo[31][31];

//* W = 서쪽, E = 동쪽 *//
int Topdown(int W, int E)
{
	if (W == 1) return E;
	if (W == E) return 1;

	int& ret = memo[W][E];
	if (ret != 0) return ret;

	for (int i = 1; i <= E; i++)
		ret += Topdown(W - 1, E - i);

	return ret;
}

int Bottomup(int W, int E)
{
	for (int i = 1; i <= E; i++)
		memo[1][i] = i;

	for(int i=2; i<=W; i++)
		for (int j = i; j <= E; j++)
			memo[i][j] = memo[i-1][j-1] + memo[i][j-1];

	return memo[W][E];
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		int N, M;
		cin >> N >> M;

		// top-down
		cout << "top-down: " << Topdown(N, M) << endl;
		// bottom-up
		cout << "bottom-up: "<< Bottomup(N, M) << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 74 day