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

문제 링크

15655번 - N과 M (6)

설명

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

단, 고른 수열은 오름차순이어야 합니다.

접근법

N개의 수 중에서 M개를 선택하되 오름차순으로 나열하는 조합(Combination) 문제입니다.

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

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

정렬된 상태에서 앞에서부터 순서대로 선택하면 자동으로 오름차순 수열이 만들어집니다.

조합을 생성하기 위해 시작 인덱스를 사용합니다.

현재 깊이에서 start 인덱스부터 N-1까지의 수를 순회하며:

1. 현재 인덱스 i의 수를 선택
2. 다음 깊이로 재귀 호출 시 시작 인덱스를 i+1로 전달
3. 깊이가 M에 도달하면 수열 출력

시작 인덱스를 i+1로 전달함으로써 이전에 선택한 수보다 뒤에 있는 수만 선택하게 되어 중복을 방지하고 오름차순을 보장합니다.

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

1. 정렬: [5, 7, 8, 9]
2. 조합 생성:
   • 5 선택 (인덱스 0) → 시작 인덱스 1부터
     • 7 선택 → “5 7” 출력
     • 8 선택 → “5 8” 출력
     • 9 선택 → “5 9” 출력
   • 7 선택 (인덱스 1) → 시작 인덱스 2부터
     • 8 선택 → “7 8” 출력
     • 9 선택 → “7 9” 출력
   • 8 선택 (인덱스 2) → 시작 인덱스 3부터
     • 9 선택 → “8 9” 출력

결과: 5 7, 5 8, 5 9, 7 8, 7 9, 8 9 (총 6개 = 4C2)

---

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 + 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, 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 + 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, 0);
  cout << out.str();

  return 0;
}