Programmers Level 2 :: 연속 부분 수열 합의 개수

하나의 수열이 주어집니다. 이 수열은 순환이 된다고 합니다. 
이 수열에서 연속적인 부분수열을 뽑았을때, 부분 수열의 합으로 나올 수 있는 모든 숫자를 구하라고 합니다.

결국 '연속된 부분 수열의 총합'을 구하라는 말인데 여기서 바로 누적합 알고리즘을 떠올려볼 수 있죠.
누적합 배열을 psum이라고 정의했을때 [i~j]에 존재하는 수열의 총합은 psum[j] - psum[i-1]로 O(1)에 계산할 수 있습니다. 그리고 이를 이용하면 O(N^2)에 모든 부분 수열을 계산할 수 있습니다.

이제 나올 수 있는 값들의 총 개수를 구해야 하는데, 간단하게 set으로 관리하면 총 시간복잡도는 O(N^2logN)이 소요됩니다. 하지만 아직 고려하지 않은 것이 있죠. 바로 수열이 순환할 수 있다는 조건입니다.

이 조건은 배열에 나머지 연산을 적용해 간단하게 구현할 수 있습니다. 하지만, 저는 좀더 쉽게 접근해봤는데요, [1, 2, 3]이라는 수열이 주어졌다고 가정해보겠습니다.

이 수열을 *2 한 배열은 [1, 2, 3, 1, 2, 3]입니다. 그리고 이 배열을 그대로 이용하면 순열의 사이클을 별도로 고려하지 않아도 됩니다. 대신 메모리를 조금 더 먹겠지요

#include <string>
#include <vector>
#include <set>
#include <cstring>
#include <iostream>
using namespace std;
set<int> s;
int psum[2010];
int solution(vector<int> elements) {
    memset(psum, 0, sizeof(psum));
    int len = elements.size();
    for(int i=0; i<len; i++) psum[i+1] = elements[i];
    for(int i=len; i<2*len; i++) psum[i+1] = elements[i-len];
    for(int i=1; i<=2*len; i++) psum[i] += psum[i-1];
    for(int i=1; i<=len; i++) {
        for(int j=0; j<len; j++) {
            s.insert(psum[i+j] - psum[i-1]);
        }
    }
    return (int)s.size();
}