[백준#C++] 에너지 모으기

문제

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

접근

1. 2가지를 뽑을 수 있는 경우의 수 중 가장 큰 수 찾기

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int arr[12];
bool check[12] = { false };
int max_num = 0;
int ans;
int sum;

void input() {
	scanf("%d",&n);
	for (int i= 0; i < n; i++) {
		scanf("%d",&arr[i]);
	}
}

void DFS(int len, int ans) {
	if (len == 2) {
		if (max_num < ans) max_num = ans;
		return;
	}

	for (int i = 1; i < n - 1; i++) {
		if (check[i]) continue;
		check[i] = true;
		int idx = i;
		int left = 0;
		int right = 0;
		while (idx < n) {
			if (check[idx] == false) {
				right = arr[idx];
				break;
			}
			idx--;
		}

		idx = i;
		while (idx >= 0) {
			if (check[idx] == false) {
				left = arr[idx];
				break;
			}
			idx++;
		}

		sum = left * right;
		DFS(len - 1, ans+sum);
		check[i] = false;
	}


}


int main() {
	//freopen("input.txt", "r", stdin);
	input();
	
	DFS(n, 0);

	printf("%d", max_num);
	return 0;
}

느낀점

• 당연히 양 옆의 수가 크면 될 줄 알고 풀었다가 시간이 많이 걸렸다.