[15664] N과 M (10)

내 코드

#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 부터 값을 비교하기때문에 ㅠ