프로그래머스 131701 - 연속 부분 수열 합의 개수 (Lv.2)

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

// 프로그래머스 131701 - 연속 부분 수열 합의 개수 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/131701

// 문제 설명
// 원형으로 이어진 수열 elements가 주어진다.
// 길이 1 이상 n 이하의 모든 연속 부분 수열의 합 중,
// 서로 다른 값이 몇 종류인지 반환하라.

// 제약 조건
// 3 <= elements 길이 <= 1,000
// 1 <= elements 원소 <= 1,000

// Example
// Input : elements = [7,9,1,1,4]
// Output: 18
//   길이 1: {1,4,7,9}, 길이 2: {2,5,10,11,16}, ... 전부 합쳐 18종류

// 접근 — 시작점 x 길이 완전탐색 + set
// 1) 시작 인덱스 i를 고정하고 길이를 1..n으로 늘리며 누적합을 갱신한다.
//    길이가 1 늘 때 원소 하나만 더하면 되므로 각 (i, len) 쌍이 O(1).
// 2) 원형이므로 인덱스는 (i + len) % n 으로 감아서 접근한다.
// 3) 합의 "종류"만 세면 되므로 set에 넣어 중복을 제거하고 크기를 반환한다.
// 시간 O(n^2 log n), 공간 O(n^2) — n <= 1,000이라 최대 100만 insert로 충분

#include <vector>
#include <set>

using namespace std;

int solution(vector<int> elements) {
    int n = elements.size();
    set<int> sums;                            // 합의 "종류"만 세면 되므로 set으로 중복 제거

    for (int i = 0; i < n; i++) {             // 시작 인덱스
        int sum = 0;
        for (int len = 0; len < n; len++) {   // 길이 1..n
            sum += elements[(i + len) % n];   // 원형: 끝을 넘으면 앞으로 감아서 이어붙임
            sums.insert(sum);
        }
    }
    return sums.size();
}

정리

• 시작점 n개 × 길이 n개 = 부분 수열이 n²개뿐이고 n이 최대 1,000이라, 완전탐색 100만 회면 끝나는 문제다. 괜히 최적화 기법부터 찾기 전에 제약부터 보고 탐색 공간을 계산하는 게 순서다.
• 같은 시작점에서 길이를 1씩 늘리면 직전 합에 원소 하나만 더하면 된다(sum += elements[(i+len) % n]). 길이마다 부분 수열을 처음부터 다시 더하면 O(n³)이 되므로, 이 누적 방식이 O(n²)을 만드는 핵심이다.
• 원형 수열은 배열을 두 배로 복사해 붙이는 방법도 있지만, 인덱스를 % n으로 감는 것만으로 같은 효과를 내고 메모리 복사가 없다.
• 문제가 묻는 건 합의 목록이 아니라 서로 다른 합의 개수다. set<int>에 던져 넣으면 중복 제거와 개수 세기가 한 번에 해결된다. 순서가 필요 없으니 unordered_set으로 바꾸면 insert가 평균 O(1)로 더 빨라지지만, 이 제약에서는 차이가 없다.
• 검증: 예제 [7,9,1,1,4] → 18 통과(MSVC /std:c++17 컴파일·실행).