내 코드
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
int field[10];
int arr[10];
bool isused[10];
int comparearr[70];
int idx;
void func(int k,int idx)
{
if(k==m)
{
for(int i = idx;i<idx+m;i++)
{
}
for(int i = 0;i<m;i++)
{
cout << arr[i] << ' ';
}
for(int i = idx;i<idx+m;i++)
{
comparearr[i] = arr[i-idx];
}
cout << '\n';
return;
}
for(int i = 0;i<n;i++)
{
if(!isused[i])
{
arr[k] = field[i];
isused[i] = 1;
idx += m;
func(k+1,idx);
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 >> field[i];
sort(field,field+n);
idx = 0;
func(0,idx);
}
- 어려웠다... 중간에 포기했다..
- 출력된 모든 배열에 대해 큰 배열에 저장해두고, 출력할때마다 큰 배열의 일부와 비교해서 꺼내려고 했지만, 시간복잡도에서 틀릴 것 같아 구현하지 않았디..
정답
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int num[10];
bool isused[10];
void func(int 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);
}
- 생각이 많아 지는 코드이다... 처음에는
이해하지 못해
직접 트리구주를 그려보면서 이해하려고 하였다..
- 재귀내에서의 반복문에 대해 다시 한번 정확한 정리를 할 필요가 있어, 다시 해보니 배열에 넣은 마지막값이랑 배열에 들어갈 값이 같으면 안된다..