[ 백준 ] 2758번 - 로또 (C++)

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

2758번: 로또

 

 

[ 문제풀이 ]

 

1. dp[ n ][ m ] 배열을 선언하고 -1로 초기화해줍니다.

 

2. n번 째 로또 번호가 m일 때의 개수를 dp 배열에 저장합니다.

 

3. 로또 번호가 m을 넘어서면 안 되므로 m의 값을 top - down을 통해 바꿔가면서 dp의 값을 초기화합니다.

 

4. 매 테스트케이스마다 m의 값을 1부터 m까지 for문을 통해 돌면서 dfs( n, m )의 값을 모두 더해 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<cmath>
#define ll long long
 
using namespace std;
 
int T, n, m;
ll dp[11][2001];
 
ll dfs(int n, int m)
{
    if (n == 1) {
        return 1;
    }
 
    ll& ret = dp[n][m];
 
    if (ret != -1) {
        return ret;
    }
 
    ret = 0;
 
    for (int i = m / 2; i >= 1; i--) {
        ret += dfs(n - 1, i);
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 1; i <= 10; i++) {
        for (int j = 1; j <= 2000; j++) {
            dp[i][j] = -1;
        }
    }
 
    for (int t = 0; t < T; t++) {
        cin >> n >> m;
 
        ll ans = 0;
 
        for (int i = m; i >= 1; i--) {
            ans += dfs(n, i);
        }
 
        cout << ans << '\n';
    }
}