[알고리즘 문제 풀기] N과 M (6)(15655)

1. 문제 풀이 아이디어

• 정렬된 수열에서 백트래킹을 이용해 현재 인덱스 이후의 수들만 선택하여 조합을 구성하고, 길이가 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[] a = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int[] result = new int[m];
    Array.Sort(a);
    Solve(0, 0);
    sw.Write(sb);

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

3. 정리

• 입력받은 수열을 오름차순 정렬한다.

• 백트래킹 함수 Solve(c, s)는 현재까지 선택한 개수 c와 시작 인덱스 s를 인자로 받는다.

• 수열의 길이가 m이 되면 출력 버퍼에 추가한다.