[Lv 2] 연속 부분 수열 합의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

 

연속 부분 수열의 합은 다음과 같다. (단, 인덱스로만 구성)

4개의 원형 수열이 존재한다면

0 1 2 3

0+1 0+2 0+3 1+2 1+3 2+3

0+1+2 0+1+3 1+2+3

0+1+2+3

 

위 값을 살펴보면 다음과 같은 규칙이 존재한다.

0, 0+1, 0+1+2, 0+1+2+3,...

따라서 합을 구한 후 배열에 삽입하고, 중복된 값을 제거 후 배열의 원소 개수를 구하면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> elements) {
    int answer = 0;
    vector<int> v;
    int start = 0, end = 0;
    
    for(int i = 0;i<elements.size();i++){
        int sum = 0;
        for(int j = i;j<i+elements.size();j++){
            int idx = j % elements.size();
            sum += elements[idx];
            v.push_back(sum);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    answer = v.size();
    return answer;
}