원형 차트
시간 제한2초메모리 제한128 MB
학급별 비율 값을 파이 차트에 배열해 경계선 두 개가 정확히 50% 차이 나서 원의 중심을 지나는 선의 최대 개수를 구합니다.
문제
민식이는 학교의 각 반에서 개를 키우는 사람이 몇 명인지 조사했다. 학교 전체에서 개를 키우는 사람은 모두 100명이므로, 어떤 반의 조사값이 15라면 그 반은 전체의 15%를 차지한다.
민식이는 이 조사값들로 원형 차트를 만들려고 한다. 각 반은 조사값에 비례하는 부채꼴 하나로 표시되며, 반들의 순서는 원하는 대로 정할 수 있다.
원형 차트에서 인접한 두 부채꼴의 경계는 원의 중심에서 원둘레로 향하는 선분이다. 두 경계가 서로 정확히 반대 방향에 있으면, 두 경계를 이은 직선은 원의 중심을 지나며 원을 둘로 나눈다. 예를 들어 경계 위치를 누적 비율로 보았을 때 두 위치의 차이가 50%이면 이런 직선 하나가 생긴다.
민식이는 반들의 순서를 적절히 정해서, 원의 중심을 지나는 직선의 개수를 최대화하려고 한다. 반의 개수와 각 반의 조사값이 주어질 때 만들 수 있는 직선 개수의 최댓값을 구하시오.
입력
첫째 줄에 반의 개수 N이 주어진다. N은 1 이상 8 이하이다.
둘째 줄에 각 반에서 개를 키우는 사람의 수 N개가 주어진다. 각 수는 100 이하의 자연수이며, 모든 수의 합은 항상 100이다.
출력
원의 중심을 지나는 직선 개수의 최댓값을 출력한다.