[BOJ] 15664번 : N과 M (10)

1. problem :

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int N, M;
int nums[8];
int ans[8];
bool isUsed[8];

void backTrack(int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) cout << nums[ans[i]] << ' '; 
		cout << '\n';
		return; 
	}
	int temp = 0; 
	int stt = 0; 
	if (k != 0) stt = ans[k - 1];
	for (int i = stt; i < N; i++) {
		if (!isUsed[i] && temp != nums[i]) {
			isUsed[i] = 1;
			ans[k] = i;
			temp = nums[i];
			backTrack(k + 1);
			isUsed[i] = 0;
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M; 
	for (int i = 0; i < N; i++) cin >> nums[i];
	sort(nums, nums + N);
	backTrack(0);

}

 

3. solution 2:

// Authored by : connieya
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/7c17e31c609d4010ad339cec1f7ed280
#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[10];
int num[10];

void func(int k, int st) {
  if (k == m) {
    for (int i = 0; i < m; ++i)
      cout << arr[i] << ' ';
    cout << '\n';
    return;
  }
  int tmp = 0;
  for (int i = st; i < n; ++i) {
    if (tmp != num[i]) { // 이전 수열의 마지막 항과 새로운 수열의 마지막 항이 같으면 중복 수열
      arr[k] = num[i];
      tmp = arr[k];
      func(k + 1, i + 1);
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; ++i)
    cin >> num[i];
  sort(num, num + n);
  func(0, 0);
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/solutions/15664.cpp

basic-algo-lecture/0x0C/solutions/15664.cpp at master · encrypted-def/basic-algo-lecture

여기서는 isUsed를 쓰지 않았다. 그 대신 int st라는 매개변수를 통해 이 과정을 다루고 있다.