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

문제 링크

15664번 - N과 M (10)

설명

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

단, 고른 수열은 비내림차순이어야 합니다.

접근법

N개의 수 중에서 M개를 선택하되 비내림차순(오름차순)으로 나열하는 조합 문제이지만, 입력에 같은 값이 여러 개 있을 수 있습니다.

두 가지를 동시에 처리해야 합니다:

1. 비내림차순 유지 (조합): 시작 인덱스 사용
2. 중복 수열 제거: 같은 깊이에서 같은 값 건너뛰기

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

백트래킹으로 조합을 생성하되, 시작 인덱스를 전달하여 이전에 선택한 것보다 뒤에 있는 수만 선택합니다.

중복 수열 제거를 위해 N과 M (9)와 동일하게 각 깊이마다 지역 변수 last를 사용합니다.

같은 깊이에서 이전에 선택한 값과 같은 값이면 건너뜁니다.

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

1. 정렬: [1, 7, 7, 9]
2. 깊이 0, 시작 0:
   • 인덱스 0 (값 1) 선택 (last = 1)
     • 깊이 1, 시작 1: 7, 7, 9 중 선택 → [1, 7], [1, 9]
   • 인덱스 1 (값 7) 선택 (last = 7)
     • 깊이 1, 시작 2: 7, 9 중 선택 → [7, 7], [7, 9]
   • 인덱스 2 (값 7) 건너뛰기 (값이 last와 같음)
   • 인덱스 3 (값 9) 선택 (last = 9)
     • 깊이 1, 시작 4: 선택 불가 (범위 초과)

결과: [1, 7], [1, 9], [7, 7], [7, 9] (4개)

만약 중복 제거를 하지 않으면:

• 인덱스 0, 1: [1, 7]
• 인덱스 0, 2: [1, 7] (중복!)
• 인덱스 1, 2: [7, 7]

last 변수로 같은 값을 가진 인덱스 2를 깊이 0에서 건너뛰어 중복을 방지합니다.

---

Code

C#

using System;
using System.Text;

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

    static void Dfs(int depth, int start) {
      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 = start; i < n; i++) {
        if (used[i] || nums[i] == last) continue;
        used[i] = true;
        seq[depth] = nums[i];
        last = nums[i];
        Dfs(depth + 1, i + 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, 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, int start) {
  if (depth == m) {
    for (int i = 0; i < m; i++)
      out << seq[i] << (i + 1 == m ? "\n" : " ");
    return;
  }

  int last = -1;
  for (int i = start; i < n; i++) {
    if (used[i] || arr[i] == last) continue;
    used[i] = true;
    seq[depth] = arr[i];
    last = arr[i];
    dfs(depth + 1, i + 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, 0);
  cout << out.str();

  return 0;
}