[알고리즘 문제 풀기] 캠프 준비(16938)

1. 문제 풀이 아이디어

• 백트래킹을 이용하여 모든 부분집합을 탐색하며 부분집합의 원소 개수가 2개 이상이고, 총합이 l 이상 r 이하이며, 최댓값과 최솟값의 차이가 x 이상이면 카운트를 증가시켜 문제를 해결한다.

2. 나의 정답 코드

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 l = int.Parse(split[1]);
    int r = int.Parse(split[2]);
    int x = int.Parse(split[3]);
    int[] a = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    Array.Sort(a);
    int result = 0;
    solve(-1, 0, 0, 0, 1000000);
    sw.WriteLine(result);
    void solve(int s, int c, int p, int max, int min)
    {
        if (c > 1 && p >= l && max - min >= x) result++;
        for (int i = s + 1; i < n; i++)
        {
            int np = p + a[i];
            if (np > r) return;
            int nmax = Math.Max(a[i], max);
            int nmin = Math.Min(a[i], min);
            solve(i, c + 1, np, nmax, nmin);
        }
    }
}

3. 정리

• 주어진 난이도 배열을 정렬하여 작은 값부터 탐색할 수 있도록 한다.

• solve 함수는 백트래킹을 통해 부분집합을 구성하며 조건을 만족하는 경우를 카운트한다.

• s는 현재 탐색 중인 인덱스를 나타내며, c는 현재까지 선택한 문제 개수를 의미한다.

• p는 현재까지의 난이도 합, max와 min은 현재 선택한 문제 중 최댓값과 최솟값을 나타낸다.

• 부분집합의 개수가 2개 이상이고, 난이도 합이 l 이상 r 이하이며, 최댓값과 최솟값의 차이가 x 이상이면 정답으로 카운트한다.

• 백트래킹을 통해 모든 경우를 탐색하며, 합이 r을 초과하는 경우 가지치기를 수행하여 불필요한 탐색을 줄인다.