[백준] 실버1 : (16198) 에너지 모으기

https://www.acmicpc.net/problem/16198

처음에는 그냥 단순하게 문제 그대로 구현하면 풀릴 줄 알았다.

쉽게 생각해 볼 수 있는 각 인덱스를 기준으로 이전 구슬 * 다음 구슬의 합이 가장 높은 인덱스를 하나씩 빼는 식으로 구현했다.

이렇게 푸니, 테스트 케이스는 모두 맞았지만 1%에서 바로 틀렸다.

 

반례를 보니, 다음과 같은 반례가 있었다.

8
10 7 8 9 10 2 4 13

Answer: 612

 

이게 어떻게 612가 나올까?

위 예시가 612가 나오는 과정은 다음과 같다.

8
10 7 8 9 10 2 4 13

-> 2 구슬 제거
10 7 8 9 10 4 13
Sum = 40

-> 4 구슬 제거
10 7 8 9 10 13
Sum = 170

-> 10 구슬 제거
10 7 8 9 13
Sum = 287

-> 9 구슬 제거
10 7 8 13
Sum = 391

-> 8 구슬 제거
10 7 13
Sum = 482

-> 7 구슬 제거
10 13
Sum = 612

 

이게 612가 나오는 과정을 계산하다 보니, 규칙을 찾기가 힘들었다.

규칙을 찾았다 하더라도 이를 코드로 옮기는 것은 복잡하고 너무 하드코딩이 될 것 같았다.

 

입력을 보면, 입력의 크기가 굉장히 작다.

계산의 핵심인 에너지 구슬의 개수가 3 <= N <= 10으로, 심지어 첫 번째와 마지막 구슬은 제외하니, 최대 8개까지 입력이 들어올 수 있다.

 

이러면 그냥 나올 수 있는 모든 경우의 수를 탐색해 보면 된다.

백트래킹의 재귀 구현이 귀찮고, 문제 난이도가 그리 높지 않아서 백트래킹으로 풀 생각을 설마 하고 안 한 것이 패착이었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void Func(vector<int> Bead, int N, int Count, int Sum, int& Answer)
{
	// 이번 경우의 수의 합과 최댓값의 max 수행
	if (Count == 2) 
	{
		Answer = max(Answer, Sum);
		return;
	}

	// 첫 번째와 마지막 구슬 제외하고 백트래킹
	for (int i = 1; i < N - 1; ++i)
	{
		if (!Bead[i]) continue;

		int temp = Bead[i]; // 기존 에너지 구슬 저장
		Bead[i] = 0;

		// 이전 에너지 구슬 구하기
		int Prev = i;
		while (true)
		{
			Prev--;
			if (Bead[Prev]) break;
		}

		// 다음 에너지 구슬 구하기
		int Next = i;
		while (true)
		{
			Next++;
			if (Bead[Next]) break;
		}

		// 이번 경우의 수의 합
		int NewSum = Bead[Prev] * Bead[Next];
		Func(Bead, N, Count - 1, Sum + NewSum, Answer);

		// 다시 기존 에너지 구슬 복구
		Bead[i] = temp;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, Answer = 0;
	cin >> N;

	vector<int> Bead(N);

	for (int i = 0; i < N; ++i)
		cin >> Bead[i];

	// 백트래킹
	Func(Bead, N, N, 0, Answer);

	cout << Answer << "\n";
}