Algorithm
[BOJ] 15663번 : N과 M (9)
rudgh99_algo
2024. 8. 18. 19:50
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
바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.
github.com
여기서는 int temp = 0;을 설정하여, 중복된 원소가 있다면, 그냥 넘겨버린다. 이게 훨씬 직관적이고 이해가 잘된다.
solution1에서는 같으면서, 사용되고 있지 않다면 쓰지 말라는 방식이고, solution2에서는 같으면 그 자리에 쓰지 마.라고 해석된다.