[BOJ] 15663번 : N과 M (9)

1. problem : 

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

 

2. solution 1 :

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

void backTrack(int k) {
	if (k == M) {
		for (int i = 0; i < M; i++) cout << ans[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 0; i < N; i++) {
		if (i > 0 && nums[i] == nums[i - 1] && !isUsed[i - 1]) { // i-1가 안쓰인다면
			continue;  // 중복된 경우 건너뛰기
		}
		if (!isUsed[i]) {
			isUsed[i] = 1;
			ans[k] = 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);
}

nums [i] == nums [i-1]이면서, ( i > 0일 때), isUsed [i-1]이 쓰이고 있다면, 나는 추가한다. 하지만, isUsed [i-1]이 쓰이고 있지 않다면, 중복된 원소가 똑같은 자리에 들어가는 꼴이니, continue 한다. 외우자..  

 

3. solution 2 :

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

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

void func(int k) { // 현재 k개까지 수를 택했음.
  if (k == m) {
    for (int i = 0; i < m; ++i) {
      cout << arr[i] << ' ';
    }
    cout << '\n';
    return;
  }
  int tmp = 0;  // 중복 수열인지 확인 하기 위해 필요한 임시 변수
  for (int i = 0; i < n; ++i) {
    if (!isused[i] && tmp != num[i]){ // 이전 수열의 마지막 항과 새로운 수열의 마지막 항이 같으면 중복 수열
      isused[i] = true;
      arr[k] = num[i];
      tmp = arr[k];
      func(k + 1);
      isused[i] = false;
    }
  }
}

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);
}

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

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

여기서는 int temp = 0;을 설정하여, 중복된 원소가 있다면, 그냥 넘겨버린다. 이게 훨씬 직관적이고 이해가 잘된다. 

 

solution1에서는 같으면서, 사용되고 있지 않다면 쓰지 말라는 방식이고, solution2에서는 같으면 그 자리에 쓰지 마.라고 해석된다.