[SW Expert Academy] 9942. 순열2 D4

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXHx5_FK0UUDFAXR

 

문제 풀이:

n이 10이기 때문에,

A를 1, 2, ..., n으로 두고, 

B에 대해 모든 순열을 대입해보면 된다.

 

void func(int state, int cur,ll sum) {
	if (cur == n) {
		if (sum + n >= k) {
			cnt++;
		}
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (state&(1 <<i)) continue;
		func(state | (1 << i), cur + 1, sum + max(cur,i));
	}
}

다음과 같이 풀 수 있다.

같은 값이 중복되어 나오면 안 되기 때문에, bit mask를 통해 사용한 숫자인지 체크한다.

 

가능한 값의 조합(A, B)을 구했다면, 이 조합들의 순열만큼의 경우의 수가 존재하기 때문에, N!*cnt가 결과 값이 된다.

 

시간 복잡도: O(n!)

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define inf 987654321
using namespace std;


typedef pair<int, int> P;
typedef long long ll;
int tc, n, k;
ll res,cnt;

void func(int state, int cur,ll sum) {
	if (cur == n) {
		if (sum + n >= k) {
			cnt++;
		}
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (state&(1 <<i)) continue;
		func(state | (1 << i), cur + 1, sum + max(cur,i));
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;

	for (int i = 1; i <= tc; i++) {
		cin >> n >> k;
		cnt = 0;
		res = 1;
		for (int j = 1; j <= n ; j++) {
			res *= j;
		}
		func(0, 1, 0);
		res = cnt*res;
		cout << "#" << i << " " << res<< '\n';
	}
	return 0;
}