문제:
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
풀이방법:
투 포인터를 사용하는 슬라이딩 윈도우랑 소수를 구하는 알고리즘 중 하나인 에라토스테네스의 체를 사용하도록 한다.
우선 자연수 N 이하의 소수들을 에라토스테네스의 체를 이용해서 찾는다. 이 때, 소수인 값들만 남기기 위해서 set을 사용해서 소수가 아닌 것들을 제거하도록 했다.
이렇게 자연수 N 이하의 소수들이 담긴 배열을 구했으면, 이를 투 포인터를 이용한 슬라이딩 윈도우를 통해서 부분합을 구한다. 자연수 N보다 부분합이 작다면 end를 움직여서 부분합을 증가시키고, 부분합이 더 크다면 start를 줄여서 부분합을 증가시킨다.
N이 되는 경우는 count를 1씩 늘리며 부분합을 줄이도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
N = int(input())
def sosu(N):
numbers = [1]*(N+1)
numbers[0]=0
numbers[1]=0
for idx in range(2,len(numbers)):
if numbers[idx] == 0:
continue
else:
numbers[idx]=idx
temp = idx+idx
while temp <= N:
numbers[temp]=0
temp+=idx
return sorted(list(set(numbers)))
so = sosu(N)
so.remove(0)
if len(so)==0:
print(0)
else:
start,end=0,0
count=0
answer = so[start]
while start<=end:
if answer < N:
end+=1
if end >=len(so):
break
answer += so[end]
elif answer >N:
answer-=so[start]
start+=1
else:
count+=1
answer-=so[start]
start+=1
print(count)
|
cs |
문제링크:
1644번: 소수의 연속합
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1786. 찾기 (0) | 2020.10.27 |
|---|---|
| [BOJ]19948. 음유시인 영재 (0) | 2020.10.15 |
| [BOJ]12100. 2048(Easy) (0) | 2020.09.24 |
| [BOJ]1806 부분합 (0) | 2020.09.22 |
| [BOJ]2096. 내려가기 (0) | 2020.09.15 |