BAEKJOON 2694 - Equal Sum Partitions

문제: https://www.acmicpc.net/problem/2694

문제

An equal sum partition of a sequence of numbers is a grouping of the numbers (in the same order as the original sequence) in such a way that each group has the same sum. For example, the sequence: 

2 5 1 3 3 7 

may be grouped as: 

(2 5) (1 3 3) (7) 

to yield an equal sum of 7. 

Note: The partition that puts all the numbers in a single group is an equal sum partition with the sum equal to the sum of all the numbers in the sequence. 

For this problem, you will write a program that takes as input a sequence of positive integers and returns the smallest sum for an equal sum partition of the sequence. 

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer M, (1 ≤ M ≤ 10000), giving the total number of integers in the sequence. The remaining line(s) in the dataset consist of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values. 

출력

For each data set, generate one line of output with the following values: The data set number as a decimal integer, a space, and the smallest sum for an equal sum partition of the sequence. 

예제 입력 

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

예제 출력 

7
21
2

힌트

출처

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

• 문제를 번역한 사람: baekjoon

  

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
 
int main()
{
    int cases, n, minSum;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        cin >> n;
        int *arr = new int[n];
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        
        for (int i = 0; i < n; i++)
        {
            minSum = 0;
            for (int j = 0; j <= i; j++)
                minSum += arr[j];
 
            int k, curSum = 0;
            for (k = i + 1; k < n; k++)
            {
                curSum += arr[k];
                if (curSum == minSum)
                    curSum = 0;
                else if (curSum > minSum)
                    break;
            }
            if (k == n && curSum == 0)
                break;
        }
        
        
        cout << minSum << endl;
        delete[] arr;
    }
 
    return 0;
}