백준 15666번 N과 M (12)

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/15666 

 

 

15666번: N과 M (12)

 

 

 

이번 문제는 백트래킹(BackTracking) 문제였습니다.

 

 

 

《문제 풀이》

 

1. 중복되는 수열을 여러 번 출력하면 안 되므로 set 컨테이너 사용 

2. s 에 입력한 숫자가 없을 경우에만 벡터 v 에 해당 숫자 삽입 

3. 비내림차순을 위해

     (1) 벡터 요소 정렬 

     (2) 인덱스를 저장할 배열에 자신의 인덱스부터 삽입

4. 현재 인덱스가 M과 같으면 v[arr[i]] 출력  

 

 

 

《C++ 코드》

 

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

using namespace std;

int N, M;
int arr[8];
vector<int> v;
	
void NandM(int idx, int start) {
	if(idx == M) {
		for(int i=0; i<M; i++) {
			cout<<v[arr[i]]<<" ";
		}
		cout<<"\n";
		return;
	}

	for(int i=start; i<v.size(); i++) {
		arr[idx] = i;
		NandM(idx + 1, i);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>N>>M;
	set<int> s; // 중복 순열 방지  
	
	for(int i=0; i<N; i++) {
		int num;
		cin>>num;
		
		if(s.find(num) == s.end()) {
			s.insert(num);
			v.push_back(num);	
		}
	}
	
	// 비내림차순 위해 정렬  
	sort(v.begin(), v.end());
	NandM(0, 0);
	
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

baekjoon - 정답 화면