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

문제 링크

15656번 - N과 M (7)

설명

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

접근법

주어진 N개의 수 중에서 중복을 허용하여 M개를 선택하는 중복순열 문제입니다.

백트래킹을 사용하여 모든 가능한 수열을 생성합니다.

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

정렬된 상태에서 작은 수부터 순서대로 선택하면 자동으로 사전 순 출력이 보장됩니다.

각 깊이에서 N개의 모든 수를 선택할 수 있습니다.

1. 현재 위치에 정렬된 배열의 모든 원소를 차례로 배치
2. 다음 깊이로 재귀 호출
3. 깊이가 M에 도달하면 수열 출력

같은 수를 여러 번 선택할 수 있으므로 방문 체크가 필요 없습니다.

예를 들어 입력이 [9, 7, 8]이고 M = 2일 때:

1. 정렬: [7, 8, 9]
2. 중복순열 생성:
   • 7 선택 → 다음 깊이
     • 7 선택 → “7 7” 출력
     • 8 선택 → “7 8” 출력
     • 9 선택 → “7 9” 출력
   • 8 선택 → 다음 깊이
     • 7 선택 → “8 7” 출력
     • 8 선택 → “8 8” 출력
     • 9 선택 → “8 9” 출력
   • 9 선택 → 다음 깊이
     • 7 선택 → “9 7” 출력
     • 8 선택 → “9 8” 출력
     • 9 선택 → “9 9” 출력

결과: 7 7, 7 8, 7 9, 8 7, 8 8, 8 9, 9 7, 9 8, 9 9 (총 9개 = 3²)

---

Code

C#

using System;
using System.IO;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] nums = new int[8];
    static int[] seq = new int[8];
    static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    static void Dfs(int depth) {
      if (depth == m) {
        for (var i = 0; i < m; i++)
          sw.Write(seq[i] + (i == m - 1 ? "\n" : " "));
        return;
      }

      for (var i = 0; i < n; i++) {
        seq[depth] = 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);
      sw.Flush();
      sw.Close();
    }
  }
}

C++

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

int n, m;
int arr[8];
int 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;
  }

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