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

문제 링크

15651번 - N과 M (3)

설명

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

접근법

1부터 N까지의 수 중에서 중복을 허용하여 M개를 선택하는 중복순열 문제입니다.

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

각 깊이에서 1부터 N까지의 모든 수를 선택할 수 있습니다:

1. 현재 위치에 1부터 N까지의 수를 차례로 배치
2. 다음 깊이로 재귀 호출
3. 깊이가 M에 도달하면 수열 출력

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

• 1 선택 → 다음 깊이
  • 1 선택 → 깊이 2 도달 → “1 1” 출력
  • 2 선택 → 깊이 2 도달 → “1 2” 출력
  • 3 선택 → 깊이 2 도달 → “1 3” 출력
• 2 선택 → 다음 깊이
  • 1 선택 → 깊이 2 도달 → “2 1” 출력
  • 2 선택 → 깊이 2 도달 → “2 2” 출력
  • 3 선택 → 깊이 2 도달 → “2 3” 출력
• 3 선택 → 다음 깊이
  • 1 선택 → 깊이 2 도달 → “3 1” 출력
  • 2 선택 → 깊이 2 도달 → “3 2” 출력
  • 3 선택 → 깊이 2 도달 → “3 3” 출력

결과: 1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3 (총 9개 = 3²)

1부터 순서대로 탐색하므로 자동으로 사전 순으로 출력됩니다.

---

Code

C#

using System;
using System.Text;

namespace Solution {
  class Program {
    static int n, m;
    static int[] seq = new int[7];
    static StringBuilder sb = new StringBuilder();

    static void Dfs(int depth) {
      if (depth == m) {
        for (var i = 0; i < m; i++)
          sb.Append(seq[i]).Append(' ');
        sb.Append('\n');
        return;
      }

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

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

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

C++

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

int n, m;
int seq[7];
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 num = 1; num <= n; num++) {
    seq[depth] = num;
    dfs(depth + 1);
  }
}

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

  cin >> n >> m;

  dfs(0);
  cout << out.str();

  return 0;
}