[bj]15650_n과m

23 Apr 2024

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

문제 접근

1~N까지 자연수 중에서 중복없이 M개 선택 (고른 수열은 오름차순)
중복없이 오름차순 -> 조합이네

문제 해결

next_permutation STL과 “원리”를 써보자 (순열은 “원리”를 안써도됨)
DFS로 해결해보자

1. pre_permutation

ref : https://twpower.github.io/90-combination-by-using-next_permutation

원리 : 1과 0의 크기 중, 1은 크기가 모두 같음을 활용

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main (){

	// 1부터 6까지 담을 벡터
	vector<int> n;

	// 1부터 6까지 생성
	for(int i=0; i<6; i++){
		n.push_back(i+1);
	}

	// 0과1을 저장 할 벡터 생성
	vector<int> ind;

	// k=4, 4개를 뽑으니까
	int k = 4;

	// k개의 1 추가
	for(int i=0; i<k; i++){
		ind.push_back(1);
	}

	// 2개(6개-2개)의 0 추가
	for(int i=0; i<n.size()-k; i++){
		ind.push_back(0);
	}

	// 정렬
	sort(ind.begin(), ind.end());

	//순열
	do{
		// 출력
		for(int i=0; i<ind.size(); i++){
			if(ind[i] == 1){
				printf("%d ", n[i]);
			}
		}

		printf("\n");

	}while(next_permutation(ind.begin(), ind.end()));

	return 0;

}

2. DFS

#define _CRT_SECURE_NO_WARNINGS


#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

using namespace std;


vector<int> graph;
int N, M; // n_C_m

void DFS(int selected[], int idx, int cnt) {
	if (cnt == M) {
	for (int i = 0; i < N; i++) {
			if (selected[i] == 1) {
				cout << graph[i] << " ";
			}
		}
		cout << endl;
		return;
	}
	else {
		for (int i = idx; i < N; i++) {
			if (selected[i] == 1) continue;

			selected[i] = 1;
			//ans.push_back(graph[i]);

			DFS(selected, i,cnt + 1);
			 
			//ans.pop_back();
			selected[i] = 0;
		}
	}

}

int main() {
	freopen("텍스트.txt", "r", stdin);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		graph.push_back(i + 1);
	}
	
	int selected[8] = { 0, };
	DFS(selected, 0, 0 );

	return 0;
}