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

문제 링크

15652번 - N과 M (4)

설명

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

접근법

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

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

현재 숫자를 선택한 후 다음 재귀 호출 시 현재 숫자부터 시작하면 중복이 허용되면서 비내림차순이 자동으로 보장됩니다.

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

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

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

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

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

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

  return 0;
}