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

문제 링크

15665번 - N과 M (11)

설명

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

접근법

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

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

백트래킹으로 중복순열을 생성하되, 같은 수를 여러 번 선택할 수 있으므로 방문 배열은 필요 없습니다.

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

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

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

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

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

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

• 인덱스 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) {
      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 (nums[i] == last) continue;
        seq[depth] = nums[i];
        last = nums[i];
        Dfs(depth + 1);
      }
    }

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

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