[BOJ 2758 // C++] 로또

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2758번 문제인 로또이다.
문제는 아래 링크를 확인하자.

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

2758번: 로또

idx 이상의 수를 가장 작은 수로 하면서 cnt개의 수를 고를 수 있는 경우의 수를 dp[idx][cnt]와 같이 나타내자.

 

이 때, dp[idx][cnt] = dp[idx*2][cnt-1] + dp[idx+1][cnt]와 같은 형태의 점화관계가 있음을 알 수 있다. 단, cnt=1의 경우는 dp[idx][cnt] = M-idx+1로 계산해주자. (초기값)

 

위의 점화식과 적절한 memoization을 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

int T;
int N, M;

bool possible(int idx, int cnt) {
	while (cnt > 1) idx <<= 1, cnt--;
	return idx <= M;
}

ll dp[11][2001];
int visited[11][2001];

ll func(int idx, int cnt) {
	if (visited[cnt][idx]) return dp[cnt][idx];
	visited[cnt][idx] = 1;

	if (cnt == 1) return dp[cnt][idx] = (M - idx + 1);

	int vidx = idx;
	ll ret = 0;
	while (possible(vidx, cnt)) {
		ret += func(vidx * 2, cnt - 1);
		vidx++;
	}

	return dp[cnt][idx] = ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	while (T--) {
		memset(visited, 0, sizeof(visited));
		cin >> N >> M;

		cout << func(1, N) << '\n';
	}
}