문제 ❌

합분해

후기

먼저 떠오른게 순열과 조합중에서 순열 떠오름

순열 nPr, 조합 nCr

근데 순열은 순서가 상관있는거라 순열 구현해서 제출을 딱 하면 시간초과 뜸..

그러면 방법은 DP이다.

뭐 몇개중에 몇개 뽑아서 합이 되는지 안되는지 확인할려고했는데

중간에 간과한게 0도 포함이 될 수 있다라는 것임.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 1000000000
#define endl "\n"

vector<int> v;

int N;
int K;
int Count;

void Per(int n, int r, int d)
{
	if (r == d)
	{
		// Print(v);
		Count = (Count + 1) % MAX;
	}

	for (int i = d; i < n; ++i)
	{
		swap(v[i], v[d]);
		Per(n, r, d + 1);
		swap(v[i], v[d]);
	}
}

int main()
{	
	v.reserve(200);

	for (int i = 1; i <= 200; ++i)
		v.push_back(i);

	int T;
	cin >> T;
	
	for (int i = 0; i < T; ++i)
	{
		cin >> N >> K;
		Per(N, K, 0);
	}

	cout << Count % MAX;

	return 0;
}

0도 있을 수 있기 때문에 위의 코드는 "시간초과" + "틀림"임.

분석

https://dontdiethere.tistory.com/84
여기보고 이해함.
물론 다른 풀이도 많음..
https://yabmoons.tistory.com/128 여기는 다른 풀이방법인데 중간에 삼중 for문 있는데 복잡해서 보다가 맘..

근데 tlqkf

근데 이렇게 생각을 어떻게하냐고!!

일단 나는 애송이니까 많이 문제를 보고 이해를 하는 식으로 일단은 가보자...DP너무 어렵다...

cpp 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
#define MAX 201
#define Moduler 1000000000
#define endl "\n"

ll dp[MAX][MAX];
int N;
int K;

int main()
{	
	cin >> N >> K;

	for (int i = 0; i <= K; ++i)
		dp[1][i] = i;
	
	for (int i = 2; i <= N; ++i)
	{
		for (int j = 1; j <= K; ++j)
		{
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % Moduler;
		}
	}

	cout << dp[N][K] << endl;

	return 0;
}