시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 244 169 145 76.316%

문제

어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.

예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.

양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법은 여러 가지가 있다. 이때, 합의 최솟값을 구하시오.

참고로 수열을 통째로 그룹 1개에 넣을 수 있다. 그럼 이때, 수의 합은 수열의 합이 된다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 첫째 줄에 수열의 크기 M이 주어진다. (1 ≤ M ≤ 10,000) 그 다음 줄부터는 그 수열에 들어있는 수가 주어지고, 한 줄에 10개씩 나누어서 주어진다. 따라서 마지막 줄은 수가 10개가 아닐 수도 있다. 수는 10,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 문제에서 설명한 가장 작은 합을 출력한다.

예제 입력 1

3
6
2 5 1 3 3 7
6
1 2 3 4 5 6
20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

예제 출력 1

7
21
2
W3sicHJvYmxlbV9pZCI6IjI2OTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1NjlcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWQ2Y1x1YWMwNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWI0XHViNWE0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjNzIwXHVjOWMwXHVkNTU4XHViYTc0XHVjMTFjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWFkZjhcdWI4ZjlcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViYTc0XHVjMTFjLCBcdWFjMDEgXHVhZGY4XHViOGY5XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzQ0IFx1YWMxOVx1YWM4YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMiwgNSwgMSwgMywgMywgN1x1Yzc0MCAoMiwgNSksICgxLCAzLCAzKSwgKDcpXHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWIwOThcdWIyMDRcdWJhNzQgXHVhYzAxIFx1YWRmOFx1YjhmOVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc3NCA3XHViODVjIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5N2MgXHVkNTY5XHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWFkNmNcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCZuYnNwO1x1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWNjMzhcdWFjZTBcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDFiNVx1YzlmOFx1Yjg1YyBcdWFkZjhcdWI4ZjkgMVx1YWMxY1x1YzVkMCBcdWIxMjNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2ZjIFx1Yzc3NFx1YjU0YywgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxICZsZTsmbmJzcDtUICZsZTsmbmJzcDsxLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsmbmJzcDtNICZsZTsmbmJzcDsxMCwwMDApIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwXHViMjk0IFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgMTBcdWFjMWNcdWM1MjkgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHVjMjE4XHVhYzAwIDEwXHVhYzFjXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWMyMThcdWIyOTQgMTAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNjk0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXF1YWwgU3VtIFBhcnRpdGlvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gb2YgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIGlzIGEgZ3JvdXBpbmcgb2YgdGhlIG51bWJlcnMgKGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBvcmlnaW5hbCBzZXF1ZW5jZSkgaW4gc3VjaCBhIHdheSB0aGF0IGVhY2ggZ3JvdXAgaGFzIHRoZSBzYW1lIHN1bS4gRm9yIGV4YW1wbGUsIHRoZSBzZXF1ZW5jZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuMiA1IDEgMyAzIDcmbmJzcDs8XC9wcmU+XHJcblxyXG48cD5tYXkgYmUgZ3JvdXBlZCBhczombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuKDIgNSkgKDEgMyAzKSAoNykmbmJzcDs8XC9wcmU+XHJcblxyXG48cD50byB5aWVsZCBhbiBlcXVhbCBzdW0gb2YgNy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIHBhcnRpdGlvbiB0aGF0IHB1dHMgYWxsIHRoZSBudW1iZXJzIGluIGEgc2luZ2xlIGdyb3VwIGlzIGFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gd2l0aCB0aGUgc3VtIGVxdWFsIHRvIHRoZSBzdW0gb2YgYWxsIHRoZSBudW1iZXJzIGluIHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgdGFrZXMgYXMgaW5wdXQgYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBhbmQgcmV0dXJucyB0aGUgc21hbGxlc3Qgc3VtIGZvciBhbiBlcXVhbCBzdW0gcGFydGl0aW9uIG9mIHRoZSBzZXF1ZW5jZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIGRhdGEgc2V0IGNvbnRhaW5zIGEgZGVjaW1hbCBpbnRlZ2VyIE0sICgxICZsZTsgTSAmbGU7IDEwMDAwKSwgZ2l2aW5nIHRoZSB0b3RhbCBudW1iZXIgb2YgaW50ZWdlcnMgaW4gdGhlIHNlcXVlbmNlLiBUaGUgcmVtYWluaW5nIGxpbmUocykgaW4gdGhlIGRhdGFzZXQgY29uc2lzdCBvZiB0aGUgdmFsdWVzLCAxMCBwZXIgbGluZSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgbGFzdCBsaW5lIGluIHRoZSBkYXRhc2V0IG1heSBjb250YWluIGxlc3MgdGhhbiAxMCB2YWx1ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWU6IFRoZSBzbWFsbGVzdCBzdW0gZm9yIGFuIGVxdWFsIHN1bSBwYXJ0aXRpb24gb2YgdGhlIHNlcXVlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest B번

  • 문제를 번역한 사람: baekjoon
  • 빠진 조건을 찾은 사람: jh05013
  • 문제의 오타를 찾은 사람: sky1357