[백준][1239][c++] 차트

차트 문제 링크

[내 풀이]

파이 둘레의 크기가 100임으로 이등분을 하면 크기가 50이 된다. 따라서 위 그림에 의해서 두 파이의 시작점의 합이 50이 되면 이등분이 된 것이다. N이 8이고, 주어진 파이들 중 최대 이등분선 값을 찾아야 하니 파이들을 순열 처리하면 될 것이다.

1) 파이들을 순열처리한다
2) 이중 for문을 사용해서 두 파이의 시작점의 합이 50이 되면 count해준다

[코드]

#include <iostream>
#include <vector>
#define N_MAX 9
using namespace std;

int N;
int max_value = -1;
int arr[N_MAX];

void swap_data(int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int make_chart() {
	int result = 0;
	vector<int> vec(N);
	int prev = 0;
	for (int i = 0; i < N; i++) {
		if (i == 0) {
			vec[i] = 0;
		}
		else {
			vec[i] = prev;
		}
		prev = prev + arr[i];
	}

	for (int i = 0; i < N; i++) {
		int cur_value = vec[i];
		for (int j = i + 1; j < N; j++) {
			int next_value = vec[j];
			if (cur_value + 50 == next_value) {
				result++;
				break;
			}
		}
	}
	return result;
}

void permutation(int depth) {
	if (depth == N) {
		int answer = make_chart();
		if (answer > max_value) max_value = answer;
	}
	else {
		for (int d = depth; d < N; d++) {
			swap_data(depth, d);
			permutation(depth + 1);
			swap_data(depth, d);
		}
	}
}


int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> arr[n];
	}
	permutation(0);

	cout << max_value << "\n";
}

[총평]
쉬운 순열, 브루트포스 알고리즘 인 것 같다.