코드

n = int(input())

# 소수 찾기 메소드
# 에라토스테네스의 체 활용
def find_prime(n):
    check = [False for _ in range(n+1)]
    
    # 소수를 담을 리스트
    prime = []
    
    for i in range(2, n+1):
        
        # False인 경우에만 prime에 담음
        # 사실상 반복문 내에서 i는 소수
        if check[i] == False:
            prime.append(i)
            
            # j는 i의 배수로 이루어져 있음 => 절대 소수일 수 없음 => True로 변경
            for j in range(i, n+1, i):
                check[j] = True
            
    return prime

# 부분합을 연산 메소드
def two_pointer(arr):
    cnt = 0
    start = 0
    end = 0
    
    while end <= len(arr):
        tmp = sum(arr[start:end])
        
        # n과 부분합이 같으면
        # 개수를 1 증가
        # start, end 모두 1씩 증가
        if tmp == n:
            cnt += 1
            end +=1
            start += 1
            
        # n보다 부분합이 작으면
        # end 1 증가
        # => 부분 수열의 길이가 1 증가하므로 값이 더 커짐 (주어진 arr에 있는, 부분 수열에 포함된 맨 마지막 요소의 그 다음 요소)
        # => n보다 값을 크게 하거나 같아짐을 기대할 수 있음
        elif tmp < n:
            end += 1
            
        # n보다 부분합이 크면
        # start 1 증가
        # => 부분 수열의 길이가 1 감소하므로 값이 더 작아짐 (기존 맨 앞의 요소)
        # => n보다 값을 작게 하거나 같아짐을 기대할 수 있음
        else:
            start += 1
    return cnt

prime_list = find_prime(n)
answer = two_pointer(prime_list)

print(answer)

문제 해설

에라토스테네스의 체와 투 포인터를 활용하여 풀 수 있는 문제.

특정 숫자를 그보다 작은 소수로 표현할 수 있는 경우의 수를 구하는 문제이다.

문제 풀이 순서는 아래와 같다.

  1. 에라토스테네스의 체를 활용하여 주어지는 숫자 n보다 작은 소수들로 이루어진 리스트를 생성
  2. 얻은 리스트에 투 포인터 알고리즘을 활용하여 연속된 소수의 합이 n인 경우의 수를 반환

에라토스테네스의 체를 이용하는 방법을 알지 못한다면 시간 초과가 발생할 수 있는 문제이며 그 이외의 부분은 흔한 투 포인트 문제와 별 차이가 없다. 소수 판별 로직에대한 참고는 나무위키의 설명이 매우 잘 되어있다.

에라토스테네스의 체 - 나무위키

댓글남기기

참고