⭐연속 부분 수열 합의 개수

문제 설명

철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다.

원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.
원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요.

❗제한사항

• 3 ≤ elements의 길이 ≤ 1,000
• 1 ≤ elements의 원소 ≤ 1,000

핵심 아이디어

보통 부분 수열의 합을 구할 때는, 누적합(prefix_sum) 알고리즘을 이용해서 풀 수 있다. 하지만 이 문제는 원형 수열이기 때문에 리스트를 연결시켜주는 방법을 떠올려야한다. 

• 처음에 list를 list * 2로 정의한다. 예를 들어, [7,9,1,1,4, 7,9,1,1,4] 이렇게 하면 맨 처음과 끝이 연결된 원형 수열이 된다. 
• 그리고 이중 for loop를 통해 부분 수열의 합을 삽입한다. sum(list[j:j+i+1])
• 그리고 리스트를 사용하면 시간 초과가 발생하기 때문에 set 자료구조를 활용해야 한다. + 중복제거를 위해

코드 구현

def solution(elements):
    answer = set()
    # [7, 9, 1, 1, 4, 7, 9, 1, 1, 4]
    N = len(elements)
    elements = elements * 2   
    for i in range(N): # N번 반복
        for j in range(N):
            answer.add(sum(elements[j:j+i+1]))
    return len(answer)