[알고리즘 문제 풀기] 카드 놓기(5568)

1. 문제 풀이 아이디어

• 백트래킹을 활용하여 선택한 카드를 이어붙인 문자열을 만들고, 이를 집합에 저장하여 중복을 제거한 조합의 수를 구해 문제를 해결할 수 있다.

2. 나의 정답 코드

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

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int k = int.Parse(sr.ReadLine());

    string[] card = new string[n];
    bool[] chk = new bool[n];
    HashSet<string> set = new HashSet<string>();

    for (int i = 0; i < n; i++)
    {
        card[i] = sr.ReadLine();
    }
    solve(0);
    sw.WriteLine(set.Count);

    void solve(int count)
    {
        if (count == k)
        {
            set.Add(sb.ToString());
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (chk[i]) continue;
            chk[i] = true;
            sb.Append(card[i]);
            solve(count + 1);
            sb.Remove(sb.Length - card[i].Length, card[i].Length);
            chk[i] = false;
        }
    }
}

3. 정리

• solve 함수는 재귀적으로 동작하며, k개의 카드를 선택했을 때 StringBuilder에 저장된 문자열을 집합에 추가한다.

• chk 배열을 통해 중복 선택을 방지하고, 문자열을 추가하고 제거하는 방식으로 백트래킹을 수행한다.

• 집합 set을 통해 중복 문자열을 제거하고 최종적으로 고유한 조합의 개수를 출력한다.