[알고리즘 문제 풀기] 에너지 모으기(16198)

1. 문제 풀이 아이디어

• 백트래킹을 사용하여 하나씩 에너지를 제거하며 최댓값을 갱신하는 방식으로 문제를 해결할 수 있다.

2. 나의 정답 코드

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int result = 0;
    int sum = 0;
    int count = 0;
    int n = int.Parse(sr.ReadLine());
    int[] w = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    bool[] chk = new bool[n];
    solve();
    sw.WriteLine(result);
    void solve()
    {
        if (count == n - 2)
        {
            result = Math.Max(result, sum);
            return;
        }
        for (int i = 1; i < n - 1; i++)
        {
            if (chk[i]) continue;
            chk[i] = true;
            count++;
            int s = i - 1;
            int e = i + 1;
            while (chk[s]) s--;
            while (chk[e]) e++;
            int se = w[s] * w[e];
            sum += se;
            solve();
            sum -= se;
            count--;
            chk[i] = false;
        }
    }
}

3. 정리

• 백트래킹을 사용하여 모든 경우를 탐색하며 최댓값을 갱신한다.

• chk 배열을 활용해 제거된 에너지를 추적하며 count로 종료 조건을 관리한다.

• 인접한 두 값을 찾아 곱하고 sum에 더한 후, 재귀적으로 탐색을 진행한다.

• solve() 호출 후 원래 상태로 되돌려 백트래킹을 수행한다.