TIL) 11/12 오늘은 적을 게 없어서 알고리즘 공부

오늘은 지난 개발 회고하고.. 발표하고..
생성형 AI로 프롬포트 작성해서 음악을 생성해봤다.
개발을 한 게 없어서 적을 게 없지만
지금은 할 일을 다 마친 상태로 야근 중이기 때문에 뭐라도 끄적거려본다
어차피 집가면 공부하고 다시 적어야 할 듯

---

백준 1644. 소수의 연속합 - python

문제 링크

문제 설명

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

내 풀이

뭔가 굉장히 별로인 방법인걸 알지만 슬라이딩 윈도우 구현 방식이 기억이 안나 꾸역꾸역 풀었다.
당연히 시공간 자원 많이 씀..
범위 설정을 자꾸 틀려서 연습을 많이 해야할 것 같다.
에라토스 뭐시기는 소수 구할 때 써야한다는 건 기억나는데 방법이 기억 안나서 나무위키 잠깐 봤음

# 백준 1644번 소수의 연속합

N = int(input())
answer = 0

# 예외 처리: 2 미만이면 만들 수 있는 연속 소수 합 없음
if N < 2:
    print(0)
    exit()

# 에라토스테네스의 체 (i*i부터 지우기)
temp_list = [i for i in range(N + 1)]
temp_list[0] = 0
temp_list[1] = 0

limit = int(N ** 0.5)
for i in range(2, limit + 1):
    if temp_list[i] != 0:
        start = i * i
        step = i
        for m in range(start, N + 1, step):
            temp_list[m] = 0

prime_list = [v for v in temp_list if v > 0]

# 두 포인터로 연속합 세기 (오른쪽 늘리고, N 이상이면 왼쪽 줄이기)
left = 0
right = 0
temp_sum = 0

while True:
    if temp_sum >= N:
        if temp_sum == N:
            answer += 1
        temp_sum -= prime_list[left]
        left += 1
    else:
        if right == len(prime_list):
            break
        temp_sum += prime_list[right]
        right += 1

print(answer)

아래는 gpt와 함께 코드를 효율적으로 다듬은 거다.

# 백준 1644번 소수의 연속합

N = int(input())
answer = 0

# 예외 처리: 2 미만이면 만들 수 있는 연속 소수 합 없음
if N < 2:
    print(0)
    exit()

# 에라토스테네스의 체 (i*i부터 지우기)
temp_list = [i for i in range(N + 1)]
temp_list[0] = 0
temp_list[1] = 0

limit = int(N ** 0.5)
for i in range(2, limit + 1):
    if temp_list[i] != 0:
        start = i * i
        step = i
        for m in range(start, N + 1, step):
            temp_list[m] = 0

prime_list = [v for v in temp_list if v > 0]

# 두 포인터로 연속합 세기 (오른쪽 늘리고, N 이상이면 왼쪽 줄이기)

left = 0
right = 0
temp_sum = 0

while True:
    if temp_sum >= N:
        if temp_sum == N:
            answer += 1
        temp_sum -= prime_list[left]
        left += 1
    else:
        if right == len(prime_list):
            break
        temp_sum += prime_list[right]
        right += 1

print(answer)

사실 오늘 스터디에서 두 문제를 풀어야 했지만 한 문제는 포기