[프로그래머스] 연속 부분 수열 합의 개수

---

🔗 문제 링크

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

프로그래머스

---

👩‍💻 코드

#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<int> elements) {
    int n = elements.size();
    unordered_set<int> sums;

    elements.insert(elements.end(), elements.begin(), elements.end());

    for (int length = 1; length <= n; length++) {
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int i = 0; i < length; i++) {
                sum += elements[start + i];
            }
            sums.insert(sum);
        }
    }

    return sums.size();
}

---

📝 풀이

우선 elements 벡터를 두 번 이어붙여 원형 수열처럼 만든다.

부분 수열 합을 계산 하기 위해 길이 1부터 n까지의 부분 수열을 순회한다. 👉 length

시작 위치는 0부터 n-1까지 순회한다. 👉 start

unordered_set은 중복을 포함하지 않기 때문에 각 부분 수열의 합을 계산하여 sums에 바로 추가한다.

원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수는 sums의 크기가 된다.