[알고리즘 문제 풀기] N과 M (9)(15663)

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);
    Array.Sort(a);
    bool[] chk = new bool[n];
    int[] result = new int[m];
    solve(0);
    sw.Write(sb);

    void solve(int t)
    {
        if (t == m)
        {
            sb.AppendLine(string.Join(" ", result));
            return;
        }
        int prev = 0;
        for (int i = 0; i < n; i++)
        {
            if (chk[i] || prev == a[i]) continue;
            chk[i] = true;
            result[t] = a[i];
            solve(t + 1);
            chk[i] = false;
            prev = a[i];
        }
    }
}

3. 정리

• 입력받은 N개의 숫자를 정렬한 후, 방문 여부를 저장하는 chk 배열과 조합을 저장하는 result 배열을 사용하여 탐색한다.

• solve 함수에서 M개의 숫자를 선택하면 출력 버퍼에 저장하고, 방문 여부를 변경하며 백트래킹을 수행한다.

• prev 변수를 활용하여 같은 숫자가 연속으로 선택되지 않도록 한다.