[알고리즘 문제 풀기] N과 M (5)(15654)

1. 문제 풀이 아이디어

• 백트래킹을 사용하여 중복되지 않는 조합을 생성하고 정렬된 상태에서 순차적으로 탐색하여 결과를 출력해 문제를 해결한다.

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;
        }
        for (int i = 0; i < n; i++)
        {
            if (chk[i]) continue;
            chk[i] = true;
            result[t] = a[i];
            solve(t + 1);
            chk[i] = false;
        }
    }
}

3. 정리

• Array.Sort()을 통해 사전순으로 결과를 정렬된 상태에서 탐색한다.

• 백트래킹을 이용하여 사용한 숫자를 chk 배열로 관리하며 중복을 방지한다.

• 재귀 함수 solve(t)에서 현재까지 선택된 숫자를 저장하고, m개를 선택하면 출력한다.