85. 연속 부분 수열 합의 개수

[문제]

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

프로그래머스

 

 

[풀이]

1. 원형리스트를 구현하기 위해 elements를 늘려주고

2. 연속 부분 수열의 길이마다 초기합을 구해준 뒤

3. 이전 값(start-1) 하나를 빼고 다음 값(start + length - 1)을 더하는 방식으로 합을 추가

 

def solution(elements):
    n = len(elements)
    elements = elements * 2  # 원형 리스트 구현
    answer = set()

    # 부분 수열의 길이를 1부터 n까지 처리
    for length in range(1, n + 1):
        current_sum = sum(elements[:length])  # 초기 부분합 계산
        answer.add(current_sum)
        
        # 슬라이딩 윈도우 방식으로 합 계산
        for start in range(1, n):
            current_sum = current_sum - elements[start - 1] + elements[start - 1 + length]
            answer.add(current_sum)

    return len(answer)