[15663] N과 M(9)

!·2022년 7월 17일
0

내 코드

#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) { // 현재 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);
}
  • 생각이 많아 지는 코드이다... 처음에는 이해하지 못해 직접 트리구주를 그려보면서 이해하려고 하였다..
  • 재귀내에서의 반복문에 대해 다시 한번 정확한 정리를 할 필요가 있어, 다시 해보니 배열에 넣은 마지막값이랑 배열에 들어갈 값이 같으면 안된다..
profile
개발자 지망생

0개의 댓글