[백준/C++] N과 M(12)

유형	난이도	완료일	링크	특이사항
백트래킹	실버2	23/04/03	https://www.acmicpc.net/problem/15666

 

내 코드

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

using namespace std;

int arr[10001];
int n, m;

vector <int> box;

void DFS(int idx, int depth)
{
	
	if(depth > m)
	{
		for(int a: box)
			cout<< a << " ";
		cout<<"\\n";
		return;
	}

		
	for(int i= idx; i<10001; i++)
	{
		if(arr[i]==0)
			continue;
		
		arr[i]--;
		
		box.push_back(i);
		
		DFS(i,depth+1);	
		
		box.pop_back();
		
		arr[i]++;
	}
}

int main(void)
{
	cin >> n >> m;
	
	int k;
	for(int i=0; i<n; i++)
	{
		cin >> k;
		arr[k]+=10001;
	}	
	
	
	DFS(0,1);
}

  이전 문제 N과M(9)와 다른 점은 같은 수를 여러번 사용해도 되며 수열이 비내림차순이어야 한다는 점 이었다.

같은 수를 여러번 사용할 수 있으므로 중복된 입력을 받아도 한 번만 입력 받은 것과 차이가 없다. 따라서 한 번 입력 받았을 때 그 수에 10001을 부여해서 M이 최대일 때 같은 수가 M번 출력 될 수 있게 수정했다. 비내림차순이므로 DFS를 호출하는 반복문의 반복자 i를 파라미터 idx에서부터 시작하도록 설정한다. 이전 코드와 고칠 점이 많이 없어 정답률도 80퍼센트로 아주 높았다.