질문
동네 모임에 참여하는 것을 좋아하는 주희는 이번 기회에 부녀회 회장이 되고 싶어 각계 인사들을 초청해 동네 모임을 주최한다.
이 아파트에 살기 위해서는 “a층의 b호에 살고 싶으면 1호실부터 1층까지 그 층에 있는 사람의 수를 합한 수만큼의 인원을 들여와야 한다”는 조건이 있다.
방 b.” 아래 (a-1 )”. 머물다 들어오셔야 합니다.
아파트에 빈집이 없고 모든 거주자가 이 계약 조건을 준수한다고 가정할 때 주어진 양의 정수 k와 n에 대해 n층 k층에 몇 명이 살고 있는지 출력합니다.
그러나 아파트는 0층부터 시작하고 각 층은 1호실부터 시작하며 i는 0층 i호실에 살고 있습니다.
입력하다
첫 번째 줄은 테스트 케이스의 수 T를 제공합니다.
각각의 경우에 첫 번째 줄은 정수 k를, 두 번째 줄은 정수 n을 제공합니다.
인쇄
각 테스트 케이스에 대해 해당 주택의 거주자 수를 출력하십시오.
이것은 메모리를 사용하는 DP 문제입니다.
메모리 사용을 명시적으로 언급합니다.
“a층 b동에 살고 싶으면 아래층 1동에서 b동까지의 인원수를 합한 수만큼 사람을 데려와야 한다(a- 1)”
0층부터 14층까지, 1층부터 14층까지 차례대로 채우세요.
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy() = { -1,0,1,0 }, dx() = { 0,1,0,-1 }, INF = 987654321;
using namespace std;
int TC, k, n, dp(15)(15);
int main() {
FAST;
cin >> TC;
for (int i = 0; i <= 14; i++)dp(0)(i) = i;
REP(i, 14) {
for (int j = 1; j <= 14; j++) {
for (int k = 1; k <= j; k++) {
dp(i)(j) += dp(i - 1)(k);
}
}
}
while (TC--) {
cin >> k >> n;
cout << dp(k)(n) << "\n";
}
}