레이팅 미적용소들은 농부 존(Farmer John)의 손아귀에서 벗어나기 위한 대담한 계획을 세웠다. 소들은 작은 고무보트를 구하는 데 성공했고, 밤의 어둠을 틈타 한 무리의 소가 보트에 올라 농장 경계의 강을 노 저어 건널 것이다. 계획은 완벽해 보였지만, 소들은 작은 고무보트가 그리 많은 무게를 견디지 못할 수도 있다는 것을 깨달았다!
N마리 (1 <= N <= 20)의 소의 무게는 w_1 ... w_N이다. 어떤 무리가 보트를 가라앉히지 않을 만큼 가벼운지 알아보기 위해, 소들은 무리의 무게를 모두 더해 본다. 안타깝게도 소들은 산수에 몹시 서툴러서, 무리에 속한 소들의 무게를 더할 때 (일반적인 10진법 덧셈에서) 받아올림이 하나라도 발생하면, 소들은 포기하고 그 무리는 보트를 타기에 너무 무겁다고 결론짓는다. 받아올림 없이 무게를 더할 수 있는 무리는 보트에 탈 수 있을 만큼 가볍다고 간주된다.
소들이 보트에 탈 수 있다고 믿는 가장 큰 무리의 크기(즉, 받아올림 없이 무게를 모두 더할 수 있는 가장 큰 무리)를 구하는 것을 도와주자.
첫째 줄: 소의 수 N (1 <= N <= 20).
둘째 줄부터 N+1번째 줄까지: 각 줄에 소 한 마리의 무게가 주어지며, 이는 1...100,000,000 범위의 정수이다.
받아올림 없이 무게를 모두 더할 수 있는 가장 큰 무리에 속한 소의 수.
escape.in · 출력을 쓸 파일 escape.out5
522
6
84
7311
193Input details: There are 5 cows, with weights 522, 6, 84, 7311, and 19.
Output details: The three weights 522, 6, and 7311 can be added together with no carries: 522 + 6 + 7311 = 7839.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Bronze