[백준 DP] 1010번 - 다리 놓기

1010번 - 다리 놓기 

 

<문제>

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

1010번: 다리 놓기

 

<문제 풀이>

 

점화식: dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1]

n 값이 1일 때, 경우의 수는 m의 값을 따른다.

n == m 일 때, 경우의 수는 1이다.

 

<코드>

#include <iostream>
#define MAX 31
using namespace std;

int T, N, M;
long long dp[MAX][MAX] = {0, };

int site(int n, int m) {
	if (n == 1)
		return dp[1][m]; 

	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (i == j) dp[i][j] = 1; //N, M의 값이 같을 때, 경우의 수는 오직 1개만 존재함
			else if (i < j) {
				dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
			}
		}
	}

	return dp[n][m];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> N >> M;

		for (int i = 1; i <= M; i++) {
			dp[1][i] = i; //N = 1일 때, 경우의 수는 M의 값을 따름
		}

		int re = site(N, M);
		cout << re << '\n';
	}

	return 0;
}

 

<결과>

 

 

2022.12.18