백준 15663 N과 M(9)

n과 m 시리즈 중에서 제일 어려운 문제인거 같다 ㅎㅎ

이 문제는 중복 없이 수열을 골라야하는데, 같은 숫자들도 들어온다.

 이 문제의 해결방식은 sort를 사용했을 때 트리구조로 정렬이 된 모습을 생각해봐야한다.

이전 수열의 마지막 항과 새로 추가하려는 값이 같으면 중복된 수열이 된다는 것이었다.

 

이건 구글의 도움을 받았다. 이걸 어떻게 떠올리지?

그러니까 재귀호출 전에 추가한 값이랑 지금 추가하려는 값이 만약 같다면,,, 중복이 되는건 당연하지! 정렬이 되어있는 상태니까,

 

만약 ㅁㅁㅁ 에 1, 7 상태에 마지막으로 9를 추가하고 1,7,9 를 출력했다 하자. 9가 2개라 하면 그 재귀가 끝난 후 돌아와 다시 마지막 ㅁ에 초가할 때 9를 추가하겠지? 그럼 또 1,7,9 를 출력하는 것임.

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

using namespace std;

int cnt = 0;
int n,m;
int arr[10];
int isused[10];
int isused_num[10];
int buffer[10];

void func(int cur)
{
	if (cur == m)
	{
		for(int i =0; i< m; i++)
		{
			cout<<buffer[i]<< ' ';
		}
		cout<<'\n';
		return;
	}
  int before = 0;
	for(int i = 0; i< n; i++)
	{
    if(isused[i] != 1 && before != arr[i])
    {
      buffer[cur] = arr[i];
      before = buffer[cur];
      isused[i] = 1;
    
      func(cur+1);
      isused[i] = 0;
    }
  }
}

int main()
{
	cin>>n>>m;
	for(int i =0; i< n; i++)
		cin>>arr[i];
	sort(arr, arr+n);
	func(0);
	return 0;
}