연속 부분 수열 합의 개수

def solution(elements):
    answer = set()
    sz = len(elements)
    
    # 누적합 구해두기
    dp = [0 for i in range(sz+1)]
    total = 0
    for idx, item in enumerate(elements):
        total += item
        dp[idx+1] = total
    
    # 부분수열 길이 순회
    for i in range(1,sz+1):
        for k in range(1, sz+1):
            result = 0
            if k-i < 0:
                result += dp[k]
                result += sum(elements[k-i:])
            else:
                result += dp[k] - dp[k-i]
            answer.add(result)
    return len(answer)

• n=1000으로 상대적으로 원소개수가 적어서 안심될 수 있으나, 생각나는 로직이 O(n^3)으로 만만치 않았음.
  연속 부분수열의 합을 구하는 과정에서 쓰인 합이 계속 사용되고 있으므로

  누적합 개념을 이용해서 값을 재사용하면 시간을 많이 줄일 수 있을 것이라 생각.

• 순환하는 값의 부분수열 합을 계산하는 방법의 아이디어는

  1. 기존배열*2를 해서 계산하는 방법
  2. substring [음수:] 이런 식으로 거꾸로 참조하는 방법

  2번의 방법이 신경써야 하는 부분이 적어질 것 같아 선택했다.

출처: 프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges