백준 15657 N과 M (8) C++

https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

이전 글과 마찬가지로 취약한 분야 복기

https://smallpants.tistory.com/219

 

거의 똑같은 문제지만 같은곳을 여러번 방문해도 되므로 visited 미사용

비내림차순이므로 일단 오름차순 정렬하고 시작

 

문제는 같은 수열을 여러번 출력하면 안됨

예를들어 { 1, 7, 8, 9 }가 들어있으면 { 1, 7 }이 출력됐으면 { 7, 1 }은 출력되면 안됨

 

그러니 for문에서 처음부터 선택하면 안되고 본인 위치부터 선택 시작해야함

그 정보를 넘겨주는 방법에 대해 고민하다가 재귀 매개변수로 start를 넘겨주고 

다음 재귀에서 for문을 start부터 시작하게 작성

 

전역변수에 start를 쓸까 생각했는데 M이 3개라면 count = 2에서 count = 1로 돌아올때 값 처리가 또 복잡해서

돌아가는 개념이 있다면 재귀구나 해서 매개변수로 넣어서 처리함

 

정답코드

#include <bits/stdc++.h>
using namespace std;

vector<int> vec, temp;
int N, M;
void recursion(int count, int start)
{	
	if (count == M) {
		for (int t : temp) { cout << t << ' '; }
		cout << '\n';
		return;
	}

	for (int i = start; i < N; i++) {
		temp[count] = vec[i];
		recursion(count + 1, i);
	}
}

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

	cin >> N >> M;
	vec.resize(N);
	temp.resize(M);

	for (int i = 0; i < N; i++) { cin >> vec[i]; }
	sort(vec.begin(), vec.end());

	recursion(0, 0);

	return 0;
}