시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 279 68 59 69.412%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 첫째 줄에 수열의 크기 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+XHJcblxyXG48cD5cdWNjMzhcdWFjZTBcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDFiNVx1YzlmOFx1Yjg1YyBcdWFkZjhcdWI4ZjkgMVx1YWMxY1x1YzVkMCBcdWIxMjNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2ZjIFx1Yzc3NFx1YjU0YywgXHVjMjE4XHVjNzU4IFx1ZDU2OVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxICZsZTsmbmJzcDtUICZsZTsgNTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7Jm5ic3A7TSAmbGU7Jm5ic3A7MTAsMDAwKSBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWFkZjggXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjRlNFx1YzViNFx1Yzc4OFx1YjI5NCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIDEwXHVhYzFjXHVjNTI5IFx1YjA5OFx1YjIwNFx1YzViNFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYyBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNzQwIFx1YzIxOFx1YWMwMCAxMFx1YWMxY1x1YWMwMCBcdWM1NDRcdWIyZDAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjMjE4XHViMjk0IDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjY5NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVxdWFsIFN1bSBQYXJ0aXRpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBlcXVhbCBzdW0gcGFydGl0aW9uIG9mIGEgc2VxdWVuY2Ugb2YgbnVtYmVycyBpcyBhIGdyb3VwaW5nIG9mIHRoZSBudW1iZXJzIChpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgb3JpZ2luYWwgc2VxdWVuY2UpIGluIHN1Y2ggYSB3YXkgdGhhdCBlYWNoIGdyb3VwIGhhcyB0aGUgc2FtZSBzdW0uIEZvciBleGFtcGxlLCB0aGUgc2VxdWVuY2U6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbjIgNSAxIDMgMyA3Jm5ic3A7PFwvcHJlPlxyXG5cclxuPHA+bWF5IGJlIGdyb3VwZWQgYXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbigyIDUpICgxIDMgMykgKDcpJm5ic3A7PFwvcHJlPlxyXG5cclxuPHA+dG8geWllbGQgYW4gZXF1YWwgc3VtIG9mIDcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBwYXJ0aXRpb24gdGhhdCBwdXRzIGFsbCB0aGUgbnVtYmVycyBpbiBhIHNpbmdsZSBncm91cCBpcyBhbiBlcXVhbCBzdW0gcGFydGl0aW9uIHdpdGggdGhlIHN1bSBlcXVhbCB0byB0aGUgc3VtIG9mIGFsbCB0aGUgbnVtYmVycyBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHRha2VzIGFzIGlucHV0IGEgc2VxdWVuY2Ugb2YgcG9zaXRpdmUgaW50ZWdlcnMgYW5kIHJldHVybnMgdGhlIHNtYWxsZXN0IHN1bSBmb3IgYW4gZXF1YWwgc3VtIHBhcnRpdGlvbiBvZiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDUwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuIFRoZSBmaXJzdCBsaW5lIG9mIGVhY2ggZGF0YSBzZXQgY29udGFpbnMgYSBkZWNpbWFsIGludGVnZXIgTSwgKDEgJmxlOyBNICZsZTsgMTAwMDApLCBnaXZpbmcgdGhlIHRvdGFsIG51bWJlciBvZiBpbnRlZ2VycyBpbiB0aGUgc2VxdWVuY2UuIFRoZSByZW1haW5pbmcgbGluZShzKSBpbiB0aGUgZGF0YXNldCBjb25zaXN0IG9mIHRoZSB2YWx1ZXMsIDEwIHBlciBsaW5lLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSBsYXN0IGxpbmUgaW4gdGhlIGRhdGFzZXQgbWF5IGNvbnRhaW4gbGVzcyB0aGFuIDEwIHZhbHVlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgZ2VuZXJhdGUgb25lIGxpbmUgb2Ygb3V0cHV0IHdpdGggdGhlIGZvbGxvd2luZyB2YWx1ZTogVGhlIHNtYWxsZXN0IHN1bSBmb3IgYW4gZXF1YWwgc3VtIHBhcnRpdGlvbiBvZiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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