25943번 - 양팔저울 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 771 | 518 | 434 | 68.454% |
문제
$1$부터 $n$까지 번호가 매겨진 $n$개의 자갈이 있다. 이 자갈들을 다음 절차에 따라 양팔저울에 올려놓는다.
- $1$번 자갈을 왼쪽, $2$번 자갈을 오른쪽에 올려놓는다.
- $i = 3, \dots , n$번 자갈 각각에 대해서 차례로 다음 과정 중 하나를 수행한다.
- 만약 양팔저울이 평형을 이루는 경우, $i$번 자갈을 왼쪽에 올려 놓는다.
- 만약 양팔저울이 평형을 이루지 않는 경우, $i$번 자갈을 가벼운 쪽에 올려 놓는다.
모든 자갈을 위의 규칙에 따라 올려 놓은 후에도 양팔저울은 평형을 이루지 않을 수 있다. 이경우 가벼운 쪽에 무게추를 올려서 균형을 맞추려고 한다. 무게추는 1g, 2g, 5g, 10g, 20g, 50g, 100g 7종류가 있고, 무게추의 개수에는 제한이 없다.
입력 받은 자갈을 위 규칙에 따라 양팔저울에 올렸을 때, 최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 개수를 구하는 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 첫 번째 줄에 자갈 개수를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10\,000$)이 주어진다. 다음 줄에 $n$ 개의 수들이 주어지는데, 이들은 번호 순서대로 자갈의 무게이다. 자갈의 무게는 각각 $1$이상이며, 모든 자갈의 무게의 총합은 $10\,000\,000$이하이다.
출력
출력은 표준출력을 사용한다. 최종적으로 평형을 맞추는데 추가적으로 필요한 무게추의 최소 개수를 한 줄에 출력한다.
예제 입력 1
7 3 1 4 1 5 9 2
예제 출력 1
2
예제 입력 2
4 2 4 6 4
예제 출력 2
0
예제 입력 3
5 2 5 3 1 2
예제 출력 3
1
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호