[BOJ]백준 16198번: 에너지 모으기

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

16198번: 에너지 모으기

난이도 쉬운 백트래킹 문제이다

백트래킹 문제의 특성은 주로 두 가지인데

① 조합&완탐을 이용한다 ② 재귀함수를 이용하여 함수 호출 전과 후에 체크 배열 값을 바꾼다

 

이 문제에서는 두 가지가 직관적으로 보이기 때문에 쉽게 문제를 풀 수 있었다

재귀함수의 인자로 현재까지의 sum값 + 직전에너지*다음에너지 를 보내주고, depth가 최대일 때 최대값을 갱신해주면 끝!

#include <cstdio>
#include <algorithm>
using namespace std;
int n, w[1001], ans;
bool chk[1001];
void func(int x, int dep) {
	if (dep == n - 2) {
		ans = x > ans ? x : ans;
		return;
	}
	for (int i = 1, p, r; i < n - 1; i++) {
		if (!chk[i])continue;
		p = i - 1; r = i + 1;
		chk[i] = 0;
		while (!chk[p])p--; while (!chk[r])r++;
		func(x + w[p] * w[r], dep + 1);
		chk[i] = 1;
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &w[i]);
	fill(chk, chk + n, true);
	func(0, 0);
	printf("%d", ans);
	return 0;
}