[Silver III] N과 M (2) - 15650

문제 링크

문제 링크

성능 요약

메모리: 2024 KB, 시간: 0 ms

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;


auto compare = [](int a, int b) {
	for (int i = 1; i <= 8; i++) {  
		int bitA = a & (1 << (i - 1)); 
		int bitB = b & (1 << (i - 1)); 
		if (bitA != bitB)  // a와 b의 비트 1부터 비교
			return bitA > bitB;
	}
	return false; 
};

int N; // 수열 범위
int M; // 수열 길이

set<int, decltype(compare)> sequences(compare);// 정렬, 중복제거

void solve(int curLen, int bit) {

	// 수열의 길이가 M과 같아지면=
	if (curLen == M) {
		sequences.insert(bit); // sequences에 추가
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (!(bit & (1 << (i - 1)))) // i번 bit 비활성화 체크
			solve(curLen + 1, (bit | (1 << (i - 1))));  // i번 bit 활성화
	}
}

int main() {
	cin >> N >> M;
	int bit = 0; // 8자리 초기 비트 값

	solve(0, bit); 

	for (int bit : sequences) {
		for (int i = 1; i <= N; i++) {
			if (bit & (1 << (i - 1))) // i번 bit 활성화 체크
				cout << i << " ";
		}
		cout << "\n";
	}
}