백준 15663번 N과 M (9)

 

 

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

 

 

15663번: N과 M (9)

 

 

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

 

 

 

 

《문제 풀이》

 

1. N개의 수를 중복없이 담을 v 벡터 

2. 중복된 수만큼 사용하기 위해 cnt[10000] 배열 선언

3. result[0] 부터 시작하기 위해 NandM(0) 호출

4. result 배열에 수를 저장할 때마다 cnt[v[i]]-- 

5. 재귀 호출 후, 다시 cnt[v[i]]++ 

 

 

 

《C++ 코드》

 

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

using namespace std;

int N, M;
vector<int> v;
int result[8];
int cnt[10000];

void NandM(int idx){
	if(idx == M){
		for(int i=0; i<M; i++){
			cout<<v[result[i]]<<" ";
		}
		cout<<"\n";
		return;
	}
	
	for(int i=0; i<N; i++){
		if(cnt[v[i]]){ //0이 아니라면  
			result[idx] = i;
			cnt[v[i]]--;
			NandM(idx+1);
			cnt[v[i]]++; //재귀호출 후 다시 증가  
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>N>>M;
	
	for(int i=0; i<N; i++){
		int num;
		cin>>num;
		
		if(cnt[num] == 0){ //0이라면  
			cnt[num] = 1;
			v.push_back(num);
		}
		else{ //0이 아니라면 벡터에 저장하지 않음  
			cnt[num]++;
		}
	}
	
	sort(v.begin(), v.end());
	NandM(0);
		
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

 

baekjoon - 정답 화면