Search
Duplicate

다리 놓기 (1010)

생성일
2021/03/20 18:19
태그

문제

풀이

그냥 조합문제이다.
일반항 : nCr = n-1Cr-1 + n-1Cr
base case : n == r || r == 0

구현

#include <iostream> #include <vector> using namespace std; int west; int east; int dp[31][31]; void pre() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } void input() { cin >> west >> east; } int rec(int n, int r) { if (dp[n][r]) return (dp[n][r]); if (n == r || r == 0) return (1); dp[n][r] = rec(n - 1, r) + rec(n - 1, r - 1); return (dp[n][r]); } void solve() { cout << rec(east, west) << endl; } int main() { int t; pre(); cin >> t; while(t--) { input(); solve(); } return (0); }
C++
복사