내 코드
#include <iostream>
using namespace std;
int field[10];
int arr[10];
bool used[10];
int n,m;
void func(int k,int x)
{
if(k==m)
{
for(int i =0;i<m;i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
int temp = 0;
for(int i = 0;i<n;i++)
{
if(!used[i] && temp!=field[i] && field[i] >= x)
{
used[i] = 1;
arr[k] = field[i];
temp = arr[k];
func(k+1,temp);
used[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);
func(0,0);
}
- 이전에 해결했던 백준 [15663] 문제와 유사하면서도, 오름차순이라는 조건이 붙었다.
func()
함수에 이전에 arr
배열에 추가한 값을 인자로 넘겨 그 인자보다 크거나 같은 값만 arr
배열에 넣을 수 있도록 구현하였다.
정답
#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);
}
- 이전 값과 관련된 것을 인자로 넘긴다는 것은 비슷하지만, 값이 아닌
인덱스
를 넘김으로써 시간복잡도 면에서 좀 더 효율적인 코드이다...!
- 또한 방문배열도 필요 없다... 어차피 인덱스 +1 부터 값을 비교하기때문에 ㅠ