[백준/BOJ] 2758 로또

문제 : 2758 로또

2758번: 로또

M이하의 수중에서 N개의 수를 뽑을 때,

앞의 수보다 2배가 되는 규칙을 따를 때 경우의 수를 세는 문제이다.

앞의 수 중에서 현재수/2보다 작은 수들의 경우의 수를 모두 더하는

DP테이블을 만들어 채운 후 모두 더해 출력하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll T, N, M, arr[15][2005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i=1;i<=10;i++){
        for (int j=1;j<=2000;j++){
            ll cnt=0;
            for (int k=1;k<=j/2;k++)
                cnt+=arr[i-1][k];
            if (i==1)
                cnt=1;
            arr[i][j]=cnt;
        }
    }
    cin >> T;
    while (T--){
        cin >> N >> M;
        ll ans=0;
        for (int i=1;i<=M;i++)
            ans+=arr[N][i];
        cout << ans << "\n";
    }
    return 0;
}