[알고리즘 문제 풀기] N과 M (4)(15652)

1. 문제 풀이 아이디어

• 백트래킹을 사용하여 1부터 N까지의 숫자 중에서 중복되며 오름차순인 M개를 고르는 조합을 생성하여 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

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

    int[] result = new int[m];
    solve(0, 0);
    sw.Write(sb);

    void solve(int s, int t)
    {
        if (t == m)
        {
            sb.AppendLine(string.Join(" ", result));
            return;
        }
        for (int i = s; i < n; i++)
        {
            result[t] = i + 1;
            solve(i, t + 1);
        }
    }
}

3. 정리

• solve(0, 0)을 호출하여 조합을 생성한다.

• t == m이면 result 배열을 문자열로 변환하여 StringBuilder에 추가한다.

• solve(i, t + 1)을 호출하여 현재 선택한 숫자 이상부터 다음 숫자를 선택하도록 한다.