[백준 1644] 소수의 연속합

[BanApp]

import sys
import math

def is_prime_number(n):
    array = [True for i in range(n+1)]
    for i in range(2, int(math.sqrt(n)) + 1):
        if array[i] == True:
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1
    return [i for i in range(2, n+1) if array[i]]

n = int(sys.stdin.readline())
if n == 1:
    print(0)

elif n == 2:
    print(1)

else:
    x = is_prime_number(n)
    s = 0
    e = 0
    k = x[0]
    cnt = 0
    while s != len(x) - 1:
        if k < n:
            if e + 1 < len(x):
                e = e + 1
                k = k + x[e]

        elif k > n:
            if s + 1 <= e:
                k = k - x[s]
                s = s + 1

        if k == n:
            cnt = cnt + 1

            if e + 1 < len(x):
                e = e + 1
                k = k + x[e]

            elif s + 1 <= e:
                k = k - x[s]
                s = s + 1

        if s == e:
            if e + 1 < len(x):
                e = e + 1
                k = k + x[e]

    print(cnt)

N-Queen 문제 아직 성공못함^^
이게 골3인데 어케 n퀸이 골드5냐고^_^

이 문제는 투포인터의 기초와 Sieve of Eratosthenes(에라토스테네스의 체)만 알면 쉽게 풀 수 있다.
여기서는 입력받은 숫자의 루트 근의 +1 까지의 배수를 모두 삭제 하는 것이다.
그럼 소수만 남는다..! 소수 찾는건 현재까지 나온 방법중 이게 제일 빠를거다. 아마? 아마 맞음.
그렇게 소수만 담긴 리스트를 만들어주면 여기서 부터는 일반적인 두포인터 문제다.
s=0, e=0에서 시작해서 값이 기준값보다 작으면 e를 1증가, 기준 값보다 크면 s를 1증가 시켜서 값을 감소 시킨다.
그렇게 해서 s가 최종적으로 리스트 탐색을 마치고 나면 조건을 만족하는 원소의 개수가 몇개인지 알 수 있다.
근데 예외 처리를 2개 해주었다.
우선 n이 1부터 가능하기 때문에 n이 1일 경우에는 소수가 존재하지 않는다. 따라서 0을 출력해준다.
두번째는 내가 while문을 시작지점 즉 변수 s를 기준으로 설정해놔서 len(x)-1 이 되는 시점에 멈추도록 했다.
만약 n이 2인 경우 이는 유일무이하게 원소가 1개인 x 리스트 이다. 따라서 len(x)-1 = 0 이 된다. 즉 반복문이 실행이 안된다.
따라서 n=2 일때 1이 출력 되도록 예외 처리를 해줬다.
최종적으로 만족하는 값을 만날때 마다 cnt를 1씩 증가시켜줘서 최종적으로 cnt값을 출력해주면 정답!

[ghdcksgml1]

잘푸셨네여 ㅎㅎ

[BanApp]

아직 n퀸 못풀어서 뒹굴거리다가 저녁먹구 다시 조지러 갑니다..