[boj : 2758] 로또

www.acmicpc.net/problem/2758

2758번: 로또

문제 : n,m이 주어지고 선영이는 전에 골랐던 수카드의 2배 이상의 카드를 n 개 고를 수 있다. 수는 m까지 적혀있는 카드이다.

 

해설 : 2차원 테이블로 작은 범위의 수들을 저장해 주면서 하나씩 뽑아내 오자.

뭔 개떡같은 그림이냐고 할 수 있겠지만, ㅈㅅ하다,,,,,그림판으로 그린거라 ㅠㅠ

설명을 하자면 

 

dp[n][m] = n번째에 m이하의 수가 올수 있는 경우의 수 이다.

 

ex)dp[4][10] = 4번째에 10부터 1까지의 수가 올수 있는 경우의 수 

4번째의 수가 올수 있는 수들은 10,9,8 밖에 없다. 7이 되버리는 순간 3번째는 최대3이 와야되고 2번째는 1 그러면 1번째는 0인데 이는 존재하지 않은 경우의 수 이기 때문.

 

따라서 dp[n][m] += f(n-1,m/2) + f(n,m-1) 로 정의 하면 되겠다.

이때 주의할 점은 1번째에 올수 있는 경우는 미리 초기화를 해야되고, dp 테이블을 0이 아닌 다른 수(-1)로 초기화 해야된다는 것이다. 이유는 0인 경우의 수가 존재하면 함수는 '아 이 case에는 경우의 수가 0 이니 0을 return 해주어야지' 라고 판단을 하고 실행하여야 되는데, 에초에 0으로 초기화를 시키고 시작해 버리면 0인 경우의 수를 판단하지 못하고 return 해주지 못하기 때문에 다시 재귀함수로 들어가 버린다.

이는 시간초과를 발생시킬 수 있는 요인이다.

 

+제발제발 오버플로 생각하자, long long으로 해주자!!

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[11][2001];

void solve();
ll f(ll x, ll y);

int main()
{
	int t;
	cin >> t;

	memset(dp, -1, sizeof(dp));
	for (ll i = 1; i <= 2000; i++)
		dp[1][i] = i;
	while (t--)
		solve();
}
void solve()
{
	ll n, m;
	cin >> n >> m;

	cout << f(n, m) << "\n";
	/*for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << dp[i][j] << " ";
		cout << "\n";
	}*/
}
ll f(ll x, ll y)
{
	if (y <= 0)return 0;
	ll& ret = dp[x][y];
	if (ret != -1)return ret;

	ret = 0;
	ret += f(x - 1, y / 2);
	ret += f(x, y - 1);
	return ret;
}