[백준] 15655번 N과 M(6)

문제: 15655번: N과 M (6)

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int n, m;
int visit[10001]; // max 가 10000임
pair<int, int> curNums[8]; // max 가 8임
pair<int, int> sortedNums[8]; // max 가 8임

void Funct(int functM) {
	if (functM == m) {
		for (int i = 0; i < m; i++)
			cout << curNums[i].first << ' ';
		cout << "\n";
		return;
	}

	int start = 0; // functM 이 0일 때 시작 인덱스
	if (functM != 0) {
		start = curNums[functM - 1].second + 1; // 수가 중복되면 안 되니까 +1 해주기
	}

	for (int i = start; i < n; i++) {
		if (visit[sortedNums[i].first] == 1) continue;

		visit[sortedNums[i].first] == 1; // 방문 처리
		curNums[functM] = sortedNums[i];
		
		Funct(functM + 1);

		visit[sortedNums[i].first] == 0; // 방문 표시 없애기
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	sort(nums.begin(), nums.end()); // 오름차순 정렬
	for (int i = 0; i < n; i++) {
		sortedNums[i] = make_pair(nums[i], i); // first: 값, second: 순서
	}
	Funct(0);

	return 0;
}

 

음.. 나는 아예 pair<int, int> 형식으로 인덱스까지 같이 저장했다. 다른 코드 보니까 아예 Funct 에 현재 curNums 에 들어있는 맨 마지막 값을 같이 보냈다. 그러면 다음 단계에서 그 값과 curNums 에 현재 넣으려는 수를 비교해서 현재 값이 더 크면 넣고 아니면 continue. 이 방식이 더 간단한 것 같다.

 

 

 

참고자료:

BaaaaaaaarkingDog | [실전 알고리즘] 0x0C강 - 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹