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

문제 링크

15657번 - N과 M (8)

설명

서로 다른 N개의 자연수가 주어지는 상황에서 N과 M (1 ≤ M ≤ N ≤ 8)이 주어질 때, 중복을 허용해 M개를 고른 비내림차순 수열을 모두 사전 순으로 출력하는 문제입니다.

접근법

주어진 N개의 수 중에서 중복을 허용해 M개를 고르는 모든 비내림차순 수열을 생성해야 하므로 백트래킹을 사용합니다.

력받은 수를 정렬한 후 백트래킹을 수행하면 사전 순 출력이 보장됩니다.

중복을 허용하지만 비내림차순을 유지해야 하므로 각 단계에서 이전에 선택한 수 이상의 수만 선택합니다.

현재 인덱스의 수를 선택한 후 다음 재귀 호출 시 현재 인덱스부터 시작하면 같은 수를 다시 선택할 수 있으면서 비내림차순이 자동으로 보장됩니다.

예를 들어 수 [9, 7, 8, 5]에서 M=2일 때 정렬 후 [5, 7, 8, 9]가 되고:

• 5 선택 → 5, 7, 8, 9 중 선택 → (5, 5), (5, 7), (5, 8), (5, 9) 생성
• 7 선택 → 7, 8, 9 중 선택 → (7, 7), (7, 8), (7, 9) 생성
• 8 선택 → 8, 9 중 선택 → (8, 8), (8, 9) 생성
• 9 선택 → 9만 가능 → (9, 9) 생성

M개를 모두 선택하면 수열을 출력하고 백트래킹으로 돌아갑니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] nums = new int[8];
    static int[] pick = 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(pick[i]).Append(' ');
        sb.Append('\n');
        return;
      }

      for (var i = start; i < n; i++) {
        pick[depth] = 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];
int pick[8];
ostringstream out;

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

  for (int i = start; i < n; i++) {
    pick[depth] = 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;
}