차트
백준 1239
GOLD V
문제 내용
문제 링크
해결 방안
각 사람들의 수가 입력받아지고 입력받은 사람은 총 100명이므로, 우리는 사람 수 자체를 백분율로써 취급할 수 있다. 데이터 순서를 조작할 수 있다고 할 때, 원의 중심을 지나는 선의 개수를 최대로 만들어야 한다. 즉, 원을 이등분하는 직선의 개수가 최대가 되는 원형 차트를 만들면 되는 것이다.
원형 차트가 이등분된다는 것은 임의의 데이터 집합의 총 합이 50명이 되면, 50%씩 두 부분으로 나눌 수 있다. 이번 문제에서 요구하는 답은 데이터의 임의의 수열에 대해 인접한 수열의 합이 50이 되는 부분 수열이 최대가 되는 것을 찾는 것이기도 하다. 다행히도 데이터는 최대 8개만 주어지므로, 우리는 브루트포스를 통해 모든 결과에 대해 검사할 수 있다. 다시 말해, 임의의 수열을 만들고, 인접한 원소의 합이 50이 되는 부분 수열의 개수를 전수조사하면 된다.
데이터를 바탕으로 임의의 수열들을 만들기 위한 방법으로, swap 함수를 사용할 수 있다. 다양한 방법들이 있고 개중에는 인접한 원소의 값을 swap하여 만드는 방법도 있지만, 이번 문제에는 각 인덱스에 대해 swap으로 수열을 만드는 방식을 사용하도록 한다. 수열이 만들어졌다면 각 수열로부터 합이 50명인 집합이 몇 개 만들어지는지 일일이 확인한다. 각 수열마다 합이 50명인 부분 수열의 개수를 비교하여, 최댓값을 찾으면 문제에서 요구하는 답이 된다.
풀이 코드
#include <iostream>
using namespace std;
// 데이터의 개수와 데이터 세트
int n;
int ratio[8];
// reference operator를 활용한 두 수의 값 교환
void swap(int &s1, int &s2) {
int tmp = s1;
s1 = s2;
s2 = tmp;
}
// 각 수열에서 합이 50명이 되는 부분 수열의 개수 확인
int line_finder() {
// 0부터 각 수까지의 파이(퍼센트) 저장(범위 : [0, 100])
int pie[9] = {0};
for(int i = 0; i < n; i++)
pie[i + 1] = pie[i] + ratio[i];
// 원의 중심을 지나는 선의 개수
int line_count = 0;
// pie[n]은 무조건 100이고,
// [0, 50]일 때와 [50, 100]일 때의 선은 같으므로 n-1까지만 확인
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
// [pie[i], pie[j]]의 합이 50이 되면 원의 중심을 지나는 선이 있음
if(pie[i] + 50 == pie[j])
line_count++;
}
}
return line_count;
}
// swap을 활용한 임의의 수열 생성
int chart_maker(int depth) {
// 모든 수에 대해 적용한 후 부분 수열 개수 확인
if(depth >= n)
return line_finder();
// 부분 수열의 개수 최댓값
int max_count = 0;
// 이전 인덱스는 이미 교환이 끝난 것으로 간주해 확인하지 않음
// i가 depth면 교환하지 않고, i가 이후의 인덱스면 해당 인덱스와 수 교환
for(int i = depth; i < n; i++) {
swap(ratio[depth], ratio[i]);
max_count = max(max_count, chart_maker(depth + 1));
swap(ratio[depth], ratio[i]);
}
// 부분 수열의 개수 최댓값
return max_count;
}
int main() {
// Fast IO
cin.tie(0);
ios_base::sync_with_stdio(false);
// 데이터의 개수와 데이터 세트 입력
cin >> n;
for(int i = 0; i < n; i++)
cin >> ratio[i];
// 원의 중심을 지나는 선의 최대 개수 탐색
swap(ratio[0], ratio[1]);
cout << chart_maker(0) << endl;
return 0;
}