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

---

알고리즘 분류

• 백트래킹

---

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

---

입력 설명

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

---

출력 설명

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

예제 입력

3 1
4 4 2

4 2
9 7 9 1

4 4
1 1 2 2

---

예제 출력

2
4

1 1
1 7
1 9
7 7
7 9
9 9

1 1 1 1
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2

---

아이디어

이전에 풀었던 N과 M (9)를 조금만 응용하면 쉽게 풀 수 있다.

N과 M(9)에서 중복 수열 출력을 방지하기 위한 map부분은 그대로 놔두고 같은 숫자 출력 방지를 위한 pair <int, bool>을 제거한다. 이후 비내림차순으로 출력해 주기 위해서 현재의 cnt부터 숫자를 꺼내오고 현재의 cnt를 다음 재귀 함수의 인자로 넘겨준다.

---

알고리즘

숫자를 입력받은 벡터 vec를 오름차순으로 정렬한다.

출력할 숫자를 삽입하는 ans 벡터 크기가 m과 같아지면 현재 ans와 동일한 배열을 출력한 내역이 있는지 map에서find를 사용해서 찾고 없다면 ans를 출력하고 map에 insert 하고 리턴한다.

ans의 벡터 크기가 m보다 작다면 vec의 현재 cnt를 index로 하는 값을 ans에 삽입하고 현재 cnt를 재귀함수의 인자로 하여 재귀함수를 실행한다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
int n,m;
vector<int> vec;
vector<int> ans;
map<string, bool> mp;
void prt(int cnt)
{
	if(ans.size()==m)
	{
	    string s="";
		for(auto &b : ans)
		    s+=to_string(b)+" ";
		if(mp.find(s) ==mp.end())
		{
		    mp.insert({s,true});
		    for(int i=0;i<s.size();i++)
		        cout<<s[i];
		    cout<<"\n";
		}
		return;
	}
	for(int i=cnt;i<vec.size();i++)
	{   
	        ans.push_back(vec[i]);
		    prt(i);
		    ans.pop_back();
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0; i<n; i++)
	{
	    int temp;
	    cin>>temp;
	    vec.push_back(temp);
	}
	sort(vec.begin(), vec.end());
	prt(0);
	return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/15666

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!