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

문제 링크

15666번 - N과 M (12)

설명

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

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

접근법

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

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

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

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

백트래킹으로 중복조합을 생성하되, 시작 인덱스를 전달하여 이전에 선택한 것 이상의 인덱스만 선택합니다.

같은 수를 여러 번 선택할 수 있으므로 다음 재귀 호출 시 시작 인덱스를 현재 인덱스 i로 전달합니다. (i+1이 아님)

중복 수열 제거를 위해 각 깊이마다 지역 변수 last를 사용합니다.

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

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

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

결과: [7, 7], [7, 9], [9, 9] (3개)

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

• 인덱스 0으로 시작: [7, 7], [7, 9]
• 인덱스 1으로 시작: [7, 7], [7, 9] (중복)

같은 값을 가진 인덱스 1을 깊이 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 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 (nums[i] == last) continue;
        seq[depth] = nums[i];
        last = nums[i];
        Dfs(depth + 1, i);
      }
    }

    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];
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 (arr[i] == last) continue;
    seq[depth] = arr[i];
    last = arr[i];
    dfs(depth + 1, i);
  }
}

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