[알고리즘 문제 풀기] N과 M (3)(15651)

1. 문제 풀이 아이디어

• 재귀를 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    StringBuilder sb = new StringBuilder();
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);
    int[] result = new int[m];
    int count = 0;

    solve();

    sw.WriteLine(sb);

    void solve()
    {
        if (count == m)
        {
            for (int i = 0; i < m; i++)
            {
                sb.Append($"{result[i]} ");
            }
            sb.AppendLine();
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            result[count++] = i;
            solve();
            count--;
        }
    }
}

3. 정리

• solve() 함수는 재귀를 활용하여 가능한 모든 수열을 생성한다.

• count가 m과 같아지면 현재까지 선택한 숫자를 StringBuilder에 추가하고 종료한다.

• 1부터 n까지 순차적으로 선택하며, result 배열에 값을 저장한 후 재귀 호출을 진행한다.

• 재귀 호출이 끝나면 count를 감소시켜 이전 상태로 되돌린다.

• 모든 경우를 탐색한 후, StringBuilder에 저장된 결과를 출력한다.