P131701 질문

[lsvv1217]

연속 부분 수열 합의 개수

from collections import deque
def solution(elements):
    answer = set()
    total = sum(elements)
    answer.add(total)
    for i in range(1,len(elements)//2+1):
        dq = deque(elements)
        for _ in range(len(elements)):
            tmp = []
            for _ in range(i):
                num = dq.popleft()
                tmp.append(num)
                dq.append(num)

            answer.add(sum(tmp))
            answer.add(total-sum(tmp))

    return len(answer)

이렇게 짰는데 테케 1번만 통과하네요
첫 번째 for문으로 부분수열 개수 지정해주고
두 번째 for문으로 수열길이만큼 반복하게 만들고
세 번째 for문에서 실제로 돌리면서 숫자의 합을 구하는 방식으로 구현했습니다

로직이 잘못된 부분이나 반례가 있다면 좀 알려주세요

[0seob]

나머지는 시간초과도 아니고 틀렸다고 나오나요??

[lsvv1217]

시간초과도 있는데 틀리고 시간초과 같아요

[SangJunni]

for i in range(1,len(elements)//2+1):
일단 len(elemnts)//2+1 이라는 구간 설정이 잘못된 것으로 보입니다.
일례로 elements가 다섯개 들어왔을 때 구간이 1,3이 되는데 길이가 3과 4인 부분수열을 고려하지 못합니다.

[lsvv1217]

밑에 answer.add(total-sum(tmp))로 전체에서 1개 구한거 빼고 전체에서 2개 구한거 빼는걸로 4개랑 3개 구했습니다

[SangJunni]

찾았습니다

for _ in range(i):
   num = dq.popleft()
   tmp.append(num)
   dq.append(num)

i 가 len(elements)의 1을 제외한 약수인 경우 모든 케이스를 얻지 못합니다.
예시) len(elements)가 6이고 i가 3인 경우
elements = [1,2,3,4,5,6]
첫번째 -> [1,2,3]
두번째 -> [4,5,6]
세번째 -> [1,2,3]
네번째 -> [4,5,6]
다섯번째 -> [1,2,3]
->>>>반복만 됨