[15655] N과 M (6)

내 코드

#include <bits/stdc++.h>
using namespace std;
int n,m;
int field[10];
int arr[10];
void recursive(int k)
{
    if(k>m)
    {
        for(int i = 1;i<=m;i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1;i<=n;i++)
    {
        if(arr[k-1] < field[i])
        {
            arr[k] = field[i];
            recursive(k+1);
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i =1;i<=n;i++)
        cin >> field[i];
    sort(field,field+n+1);
    recursive(1);
}

• 중복이 없기때문에 방문 배열을 따로 선언하지 않았으며, k=1 부터 써서 arr[k] 의 값과 비교하여 값을 넣는 것으로 구현하였다.

정답

include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
bool isused[10];
int num[10];

void func(int k){ // 현재 k개까지 수를 택했음.
  if(k == m){ // m개를 모두 택했으면
    for(int i = 0; i < m; i++)
      cout << num[arr[i]] << ' '; // arr에 기록해둔 인덱스에 대응되는 수를 출력
    cout << '\n';
    return;
  }
  int st = 0; // 시작지점, k = 0일 때에는 st = 0
  if(k != 0) st = arr[k-1] + 1; // k != 0일 경우 st = arr[k-1]+1
  for(int i = st; i < n; i++){
    if(!isused[i]){ // 아직 i가 사용되지 않았으면
      arr[k] = i; // k번째 인덱스를 i로 정함
      isused[i] = 1; // i를 사용되었다고 표시
      func(k+1); // 다음 인덱스를 정하러 한 단계 더 들어감
      isused[i] = 0; // k번째 인덱스를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
    }
  }
}

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

• 중복 배열을 도입하여 구현하였다. 이를 위해 인덱스의 값을 저장하는 배열을 따로 선언하였다. 어차피 원래 수가 저장되어 있는 배열은 오름차순이기때문에 배열인덱스의 값자체도 오름차순으로 되네..