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

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

2758번: 로또

 

별로 특별해 보이지 않은 문제였다. 조합을 구하되 조건이 있는 조합이기 때문에 백트래킹으로 가지를 잘 치면 통과할 수 있을 것이라 생각했다. 그러나 계속 시간초과가 났고 구글링 해보니 dp 문제였다.

 

역시 난 dp가 약하다.. 아무튼, 

 

1 2 4 8

1 2 4 9

1 2 4 10

1 2 5 10

 

이 가능하다고 할 때, 위 조합을 잘 보면 10개 중 3개를 뽑는 개수를 포함하고 있다. 왜냐하면 

10개 중 4개를 뽑는다고 하면, 5개중 3개를 뽑는 개수를 언제나 포함하게된다.

1 2 4

1 2 5

왜냐하면 이전에 뽑은 것보다 *2이상이 되어야하기 때문이다. 그리고 여기에 10만 붙히면 새로운 확장이 된다. 

1 2 4 10

1 2 5 10

 

그리고 9개 중 4개를 뽑는 경우의 수를 더해준다. 

위는 알겠는데 이건 왜?

 

왜냐하면 여기서 9개 중 4개를 뽑는다고 하면  1 2 4 8, 1 2 4 9이다.

그리고 위와 더하면 이게 모든 경우의 수가 된다.

 

그래서 이 문제는 메모이제이션 바텀업 방식의 dp이다.

 

아~ 유연한사고와 점화식을 새우는 방법을 잘 생각해보자

 

#include <iostream>
#include <cstring>
#include <cmath>
#define ll long long
using namespace std;
ll dp[11][2001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int T, N, M;
	cin >> T;


	for (int t = 0; t < T; t++) {
		cin >> N >> M;

		memset(dp, 0, sizeof dp);
		for (int i = 1; i <= M; i++) dp[1][i] = 1;

		for (int i = 1; i <= N; i++) {
			for (int j = pow(2, i - 1); j <= M; j++) {
				dp[i][j] += dp[i - 1][j / 2] + dp[i][j - 1];
			}
		}

		cout << dp[N][M] << '\n';
	}
}