피자 나누기 - 구름LEVEL
피자 나누기
Quiz Info
피자 나누기
100points
Participant
23
Solved Rate
17.3%
0
0

 피자를 좋아하는 성준이는 먹는 것 뿐만 아니라 피자를 예쁘게 커팅하는 것도 좋아한다. 특히 피자의 중심을 지나 지름을 따라 반으로 가를 때에 성준이는 행복을 느낀다. 

 오늘도 친구들과 피자를 먹기로 한 성준이는 피자를 예쁘게 자르려고 한다. 피자는 한 판을 주문했으며 각자 피자를 먹고 싶은 비율을 퍼센트로 제시한다. 성준이는 한 명이 하나의 조각으로 정확히 희망 비율대로 피자를 받을 수 있게 자르려고 한다. 즉, N명의 인원이 총 N개의 조각을 나누어 가지며 각 피자 조각의 넓이는 친구들이 희망한 넓이와 일치해야 한다.


그림 1. 중심을 가르는 커팅선이 두 번 생기는 경우(왼쪽)와 한 번만 생기는 경우(오른쪽)


 예를 들어서 네 명의 인원이 각각 10%, 40%, 40%, 10%의 피자를 먹기로 정했다고 가정해보자. 이 경우 그림 1 처럼 여러가지 방법으로 피자 조각을 나눌 수 있다. 피자 조각의 크기를 배치하는 순서는 자유롭다. 이 때 성준이는 지름을 따라 피자를 자르는 횟수를 최대화 하려고 한다.

 N명의 인원이 나누어 받을 피자의 비율이 입력으로 주어질 때, 지름을 따라 피자를 자를 수 있는 최대 횟수를 계산하는 프로그램을 작성하시오.


입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 20이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차레로 주어진다.

 테스트케이스의 첫 줄에는 피자를 나누어 먹을 인원의 수를 나타내는 1이상 8이하의 자연수 N이 주어진다.

 두 번째 줄에는 N명이 각자 피자를 나누어 받을 비율이 공백으로 구분되어 주어진다.

  • 모든 비율은 1이상 100이하의 자연수로 주어진다. 
  • 비율의 합은 항상 100이다.


출력 형식

 각 테스트케이스에 대한 정답을 차례로 한 줄씩 출력한다.

  • 피자를 중심을 지나 지름대로 자를 수 있는 최대 횟수를 출력한다.
Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
2
4
10401040
3
105040
Output
2
1
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)