15649 문제 해결.

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

15649번: N과 M (1)

문제를 보자말자 떠올린 생각은 

어 ? 이거 저번에 써본 비트마스킹을 써볼까? 였다.

따라서 처음에는 

그냥 브루트 포스를 구현하였다.

 

bool findKey(std::deque<int>& dq, int key) {
	int i;

	i = 0;
	for (; i < dq.size(); ++i) {
		if (key == dq[i]) {
			return (true);
		}
	}
	return (false);
}

void solve(int n, int m, std::deque<int>& dq, int cnt) {
	if (m == cnt) {
		for (int i = 0; i < dq.size(); ++i) {
			std::cout<< dq[i]<< " ";
		}
		std::cout << "\n";
		return ;
	}	
	for (int i = 1; i <= n; ++i) {
		if (findKey(dq, i))
			continue ;
		dq.push_back(i);
		solve(n, m, dq, cnt + 1);
		dq.pop_back();
	}
}

처음에는 findKey라는 녀석을 통해 매번 있는지 없는지를 판단하는 로직을 사용하였기 때문에 

매번 체크마다 처리하는 로직이 존재하였는데 이를 비트마스킹을 이용해 처리하도록 

변경하였다.

 

void solve(int n, int m, std::deque<int>& dq, int cnt, int selected) {
	if (m == cnt) {
		for (int i = 0; i < dq.size(); ++i) {
			std::cout<< dq[i]<< " ";
		}
		std::cout << "\n";
		return ;
	}	
	for (int i = 1; i <= n; ++i) {
		if (selected & (1 << i))
			continue ;
		selected = selected | (1 << i);
		dq.push_back(i);
		solve(n, m, dq, cnt + 1, selected);
		dq.pop_back();
		selected = selected & ~(1 << i);
	}
}