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

문제 링크

15650번 - N과 M (2)

설명

1부터 N까지의 자연수 중에서 중복 없이 M개를 고른 오름차순 수열을 모두 출력하는 상황에서 N과 M (1 ≤ M ≤ N ≤ 8)이 주어질 때, 모든 수열을 사전 순으로 출력하는 문제입니다.

접근법

1부터 N까지 중에서 M개를 고르는 모든 조합을 생성해야 하므로 백트래킹을 사용합니다.

미리 조합의 개수를 계산할 수 없고 각 단계마다 선택 가능한 숫자가 달라지므로 재귀적으로 탐색하는 것이 적합합니다.

이때 오름차순 조합이므로 이미 선택한 숫자보다 큰 숫자만 선택합니다.

현재 숫자를 선택한 후 다음 재귀 호출 시 현재 숫자 + 1부터 시작하면 자동으로 오름차순이 보장되고 중복도 방지됩니다.

예를 들어 N=4, M=2일 때:

• 1을 선택하면 다음은 2, 3, 4 중 하나 → (1, 2), (1, 3), (1, 4) 생성
• 2를 선택하면 다음은 3, 4 중 하나 → (2, 3), (2, 4) 생성
• 3을 선택하면 다음은 4만 가능 → (3, 4) 생성
• 4를 선택하면 다음 선택 불가능 → 종료

M개를 모두 선택하면 출력하고 백트래킹으로 돌아가 다음 경우를 탐색합니다.

---

Code

C#

using System;
using System.Text;

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

      for (var num = start; num <= n; num++) {
        arr[depth] = num;
        Dfs(depth + 1, num + 1);
      }
    }

    static void Main(string[] args) {
      var line = Console.ReadLine()!.Split();
      n = int.Parse(line[0]);
      m = int.Parse(line[1]);

      Dfs(0, 1);

      Console.Write(sb.ToString());
    }
  }
}

C++

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

int n, m;
int 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;
  }

  for (int num = start; num <= n; num++) {
    seq[depth] = num;
    dfs(depth + 1, num + 1);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> m;
  dfs(0, 1);
  cout << out.str();

  return 0;
}