[Baekjoon] 1644. 소수의 연속합 [G3]
📚 문제
https://www.acmicpc.net/problem/1644
📖 풀이
N이하의 소수를 찾는다. 에라토스테네스의 체로 소수를 찾아준다.
소수를 찾을 때마다 소수의 배열에 담아준다.
소수가 순서대로 정렬되어 있으니 따로 정렬할 필요 없다.
N이하의 소수를 배열에 담고, 투포인터로 찾아준다.
s와 e를 시작점에서 같이 움직인다. 현재 합이 더 크면 e를 움직이고 그 위치에 있는 수를 더한다.
합이 작으면 s를 움직이고 움직이면서 왼쪽에 있는 수를 하나 뺀다.
s가 e를 넘거나, e가 인덱스를 넘어서면 종료한다.
📒 코드
n = int(input())
arr = [0 for _ in range(n + 1)]
sosu = []
for i in range(2, n + 1): # 에라토스테네스의 체 소수 판정
if arr[i]: # 합성수일 땐 보지 않는다.
continue
sosu.append(i) # 소수들은 sosu 리스트에 담는다.
for j in range(i * i, n + 1, i): # 소수의 배수들을 다 합성수 처리
arr[j] = 1
s, e, cnt = 0, 0, 0
if sosu: # 소수가 없는 경우 0 출력
sum_sosu = sosu[0]
while s <= e: # s가 e를 넘는 경우는 더 이상 원하는 값이 존재하지 않는다.
if sum_sosu > n: # 현재 합이 더 큰 경우
sum_sosu -= sosu[s] # s를 움직여주고 왼쪽의 수를 뺀다.
s += 1
else: # 현재 합이 작거나 같은 경우
if sum_sosu == n: # 같으면 cnt를 증가
cnt += 1
e += 1 # 합이 같거나 작을 때 e를 움직인다.(같을 땐 e나 s 둘 중 뭘 움직여도 상관 X)
if e == len(sosu): # 인덱스를 넘으면 종료
break
sum_sosu += sosu[e] # e가 움직이면 더해준다.
print(cnt)
🔍 결과
Author And Source
이 문제에 관하여([Baekjoon] 1644. 소수의 연속합 [G3]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yunhlim/Baekjoon-1644.-소수의-연속합-G3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)