[백준] 2578-로또(C++)

문제링크: https://www.acmicpc.net/problem/2758

2758번: 로또

 

Top-down 방식의 dp로 해결했습니다. 

 

 

 

 

접근방식

 

1. 문제를 보면서 일반적인 dfs로는 구현이 불가능한 것을 이해하였고, dp로 구현하기로 함

 

2.  top-down방식을 통해서 구현

 

 

문제풀이 

 

1.  일반적인 top-down방식으로 구현 

 

주의점은 숫자 범위때문에 long long으로 선언해야한다는점?

 

아래는 정답 코드

#include <iostream>
using namespace std;
int t;
int n, m;
long long dp[2001][11];

long long solved(int currentN, int currentM) {

	if (currentN == 1)
		return 1;

	long long& ret = dp[currentM][currentN];
	if (ret != -1)
		return ret;
	ret = 0;
	for (int i = currentM/2; i >= 1; i--) {
		ret += solved(currentN - 1, i);
	}

	return ret;
}

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

	cin >> t;
	while (t--) {
		cin >> n >> m;

		for (int i = 1; i <= 2000; i++)
			for (int j = 1; j <= 10; j++)
				dp[i][j] = -1;

		long long result = 0;
		for (int i = m; i >= 1; i--)
			result += solved(n, i);

		cout << result  << "\n";

	}


	return 0;
}