[백준 15663] N과 M (9) (C#, C++) - soo:bak

문제 링크

15663번 - N과 M (9)

설명

중복된 값이 있을 수 있는 N개의 자연수와 자연수 M (1 ≤ M ≤ N ≤ 8)이 주어지는 상황에서, N개의 자연수 중에서 M개를 고른 수열을 중복 없이 모두 사전 순으로 출력하는 문제입니다.

접근법

N개의 수 중에서 M개를 중복 없이 선택하는 순열 문제이지만, 입력에 같은 값이 여러 개 있을 수 있습니다.

이 경우 같은 값을 가진 서로 다른 인덱스를 사용하면 동일한 수열이 여러 번 생성됩니다.

예를 들어 [1, 7, 7]에서 2개를 선택할 때:

• 1번째 7 선택 → 2번째 7 선택: [7, 7]
• 2번째 7 선택 → 1번째 7 선택: [7, 7]

이 두 수열은 값이 같지만 인덱스가 다릅니다.

중복 수열을 방지하기 위해 다음 방법을 사용합니다:

먼저 입력받은 N개의 수를 오름차순으로 정렬합니다.

백트래킹으로 순열을 생성하되, 방문 배열로 각 인덱스의 사용 여부를 관리합니다.

핵심은 같은 깊이(레벨)에서 이전에 선택한 값과 같은 값을 다시 선택하지 않는 것입니다.

각 깊이마다 지역 변수 last를 두고, 이전에 선택한 값을 저장합니다.

현재 순회하는 값이 last와 같으면 건너뜁니다.

예를 들어 [1, 7, 7, 9]에서 M = 2일 때:

1. 정렬: [1, 7, 7, 9]
2. 깊이 0에서:
   • 1 선택 (last = 1)
   • 7 선택 (인덱스 1, last = 7)
   • 7 건너뛰기 (인덱스 2, 값이 last와 같음)
   • 9 선택 (last = 9)
3. 결과: [1, 7], [1, 7], [1, 9], [7, 1], [7, 7], [7, 9], [7, 1], [7, 7], [7, 9], [9, 1], [9, 7], [9, 7]

중복 제거 전: 12개 중복 제거 후: [1, 7], [1, 9], [7, 1], [7, 7], [7, 9], [9, 1], [9, 7] (7개)

정렬된 순서대로 탐색하고 중복을 건너뛰므로 자동으로 사전 순으로 출력됩니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] nums = new int[8];
    static bool[] used = new bool[8];
    static int[] seq = new int[8];
    static StringBuilder sb = new StringBuilder();

    static void Dfs(int depth) {
      if (depth == m) {
        for (var i = 0; i < m; i++)
          sb.Append(seq[i]).Append(' ');
        sb.Append('\n');
        return;
      }

      var last = -1;
      for (var i = 0; i < n; i++) {
        if (used[i] || nums[i] == last) continue;
        used[i] = true;
        seq[depth] = nums[i];
        last = nums[i];
        Dfs(depth + 1);
        used[i] = false;
      }
    }

    static void Main(string[] args) {
      var first = Console.ReadLine()!.Split();
      n = int.Parse(first[0]);
      m = int.Parse(first[1]);

      var line = Console.ReadLine()!.Split();
      for (var i = 0; i < n; i++)
        nums[i] = int.Parse(line[i]);

      Array.Sort(nums, 0, n);

      Dfs(0);
      Console.Write(sb.ToString());
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[8], seq[8];
bool used[8];
ostringstream out;

void dfs(int depth) {
  if (depth == m) {
    for (int i = 0; i < m; i++)
      out << seq[i] << (i + 1 == m ? "\n" : " ");
    return;
  }

  int last = -1;
  for (int i = 0; i < n; i++) {
    if (used[i] || arr[i] == last) continue;
    used[i] = true;
    seq[depth] = arr[i];
    last = arr[i];
    dfs(depth + 1);
    used[i] = false;
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;

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

  sort(arr, arr + n);

  dfs(0);
  cout << out.str();

  return 0;
}