[백준]#1644 Python

백준 1644번 파이썬

https://www.acmicpc.net/problem/1644

아이디어

1. 특정 범위 내의 소수의 집합 구하기 -> 에라토스테네스의 체 이용
2. 특정 조건에 해당하는 부분수열의합 구하기 -> 투 포인터 이용

에라토스테네스의 체
https://wikidocs.net/21638

2부터 소수에 해당 -> 2 제외 모든 2의 배수 지운다 -> 3은 안지워졌으므로 소수 -> 3 제외 모든 3의 배수 지운다 -> 5는 안지워졌으므로 소수 -> ... 반복

def eratosthenes(prime_numbers, N):
    if N == 1:
        pass
    else:
        a = [False,False] + [True]*(N-1)
        for i in range(2,N+1):
            if a[i]:
                prime_numbers.append(i)
                for j in range(2*i, N+1, i):
                    a[j] = False
    return

투 포인터

start와 end 두 개의 인덱스를 기준으로 두 인덱스 사이 범위의 합이 N을 넘는 여부에 따라 어느 인덱스를 움직일지 결정.

def two_pointer(lst, end, start):
    global case
    while end < start and end >= 0:
        if sum(lst[end:start+1]) < N:
            end -= 1
        elif sum(lst[end:start+1]) > N:
            start -= 1
        else:
            case += 1
            end -= 1
    return

전체코드

import sys
input = sys.stdin.readline

N = int(input())


def two_pointer(lst, end, start):
    global case
    while end < start and end >= 0:
        if sum(lst[end:start+1]) < N:
            end -= 1
        elif sum(lst[end:start+1]) > N:
            start -= 1
        else:
            case += 1
            end -= 1
    return


def eratosthenes(prime_numbers, N):
    if N == 1:
        pass
    else:
        a = [False,False] + [True]*(N-1)
        for i in range(2,N+1):
            if a[i]:
                prime_numbers.append(i)
                for j in range(2*i, N+1, i):
                    a[j] = False

    return


prime_numbers = []
eratosthenes(prime_numbers, N)

if N <= 2:
    print(len(prime_numbers)) 
else:
    case=0
    if prime_numbers[-1] == N:
        case += 1
    for i in range(len(prime_numbers)-1, 0, -1):
        if prime_numbers[i] + prime_numbers[i-1] <= N:
            prime_numbers = prime_numbers[:i+1]
            start, end = i, i-1
            break
    else:
        start, end = len(prime_numbers)-1, len(prime_numbers)-2

    two_pointer(prime_numbers, end, start)
    print(case)

느낀점

내 코드는 소수의 집합에서 바로 투 포인터를 써서 구하지 않고 먼저 끝에서부터 두 개씩 더한 값을 보며 N값보다 큰 값을 형성하는 원소들은 없애준다 -> 즉, prime_numbers에 최소 원소 2개는 있어야 함 -> N이 1이나 2일 때는 따로 생각해주어야 한다.