[C++ / 15666] N과 M (12)

문제

15666번: N과 M (12)

---

문제 설명

N개의 자연수와 자연수 M이 주어 졌을때, 다음 조건을 만족하는 길이가 M인 수열을 모두 구하면 됨.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

개인적으로 문제를 파악하기엔 중복 순열을 구하되, 비내림차순 조건을 만족하면 되겠다고 생각하고 문제를 푼 것 같다.

---

풀이 방식

내가 푼 방식을 요약하자면 다음과 같다.

1. 주어진 n개의 input값들을 오름차순으로 정렬한다.
2. 중복을 없앤다.
3. 조건에 맞게 출력한다
   • answer 배열에 카운트가 m이 되지 전까진 출력하지 않는다.
   • 그 전까진 재귀를 통해 중복순열과 비슷하되, 조건을 만족하는 값을 판단한다.

예제 2번을 예시로 들어서 입력이 다음과 같다고 하자.

4 2
9 7 9 1

이때 입력값이 9 7 9 1 이니까, 1 1 7 9로 오름차순 정렬을 한 뒤 1 7 9로 중복을 없애 준다.

그 다음 조건에 맞게 출력하기 위한 함수를 이용할 것이다.

 

이때 만약 1 7 9라는 값을 이용해 m개를 뽑는 중복순열을 만든다면 값이 다음과 같이 출력 될 것이다.

1 1
1 7
1 9
7 1 (예외)
7 7
7 9
9 1 (예외)
9 7 (예외)
9 9

하지만 몇가지 값들은 조건을 충족하지 못함으로 예외 처리를 해준다.

즉, 비내림차순에 조건에 맞게 현재값보다 다음 값이 크도록 해준다.

---

솔루션

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int idx = 0;
int num[9], save[9], ans[9];

void seq(int cnt, int cur)
{
  if (cnt == m)
  {
    for (int i = 0; i < m; i++)
      cout << ans[i] << " ";
    cout << endl;
    return;
  }

  int prev = -1;

  for (int i = cur; i < idx; i++)
  {
    ans[cnt] = save[i];
    prev = save[i];
    seq(cnt + 1, i);
  }
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;

  for (int i = 0; i < n; i++)
    cin >> num[i];

  sort(num, num + n);

  for (int i = 0; i < n; i++)
  {
    if (num[i] == num[i + 1])
      continue;
    else
    {
      save[idx] = num[i];
      idx++;
    }
  }

  seq(0, 0);
  return 0;
}

---

알게된 점

코드 막바지에 알게 된 점인데..

나는 처음에 num 배열을 통해 입력값을 받고 save 배열을 통해 오름차순 정렬과 중복값을 없애주었다.

하지만 오름차순 정렬만 해주면, seq 함수 내부에서 중복 값을 판단할 때 if문 한 줄만 써주면 되었기에 조금.. 비효율 적인 코드를 짜고 말았다 😅

 

그리고 백트래킹 이라는 알고리즘 분류에 대해서 처음 알게 되었다.

알고 문제를 푼건 아니지만 재귀를 통해 의도에 맞게 잘 해결한 거 같아서.. 뭐 잘 된거 같다 😅