[백준 파이썬] 1644 / 소수의 연속 합

백준 1644

연속된 리스트 값의 합 문제로 두 포인터를 이용해 풀면 된다. 소수 리스트를 구할 때 값들이 정렬 되어있으므로 다른 처리를 해주지 않아도 된다.

# 소수 리스트 생성 함수
def prime_list(MAX):
    prime_idx = [False, False] + [True] * (MAX-1) # 0 ~ MAX

    n = int(MAX**0.5) + 1
    for i in range(2, n):
        if prime_idx[i]:
            for j in range(i+i, MAX+1, i):
                prime_idx[j] = False

    return [i for i in range(2, MAX+1) if prime_idx[i]]

N = int(input())

# N=1 일 때는 prime_list 함수가 빈 리스트를 반환하므로 아래 코드에서 인덱스 에러가 발생한다.
if N == 1: 
    print(0)
else:
    pl = prime_list(N)
	
    start, end = len(pl)-1, len(pl)-1 # 시작과 끝 값을 리스트-1 로 초기화
    cont_sum = pl[-1] # N 이하 가장 큰 소수로 초기화
    ans = 0

    while 0 <= start <= end:
        if cont_sum < N: # 연속 합이 N 보다 작다면
            start -= 1 # 시작 인덱스를 줄여
            cont_sum += pl[start] # 연속 합 증가
        else: # 연속 합이 N보다 크거나 같을 경우
            if cont_sum == N:
                ans += 1 
                if start == end: # 연속 합이 N과 같지만 시작과 끝값이 같다면(N이 소수인 경우)
                    start -= 1 # 시작 인덱스만 줄여
                    cont_sum += pl[start] # 연속 합 크기 증가
            cont_sum -= pl[end] 연속 합에서 끝 인덱스 값 뺀 후
            end -= 1 # 끝 인덱스 감소
    print(ans)