728x90
[백준알고리즘] 1644번: 소수의 연속합 -Python
https://www.acmicpc.net/problem/1644
1644번: 소수의 연속합
문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 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이 연속이 아니기에 적합한 표현이 아니다. 또한 한
www.acmicpc.net
연속합 형태의 문제와 똑같이 풀어주나 소수를 구하는 과정이 추가된다.
다른 부분들을 똑같이 하더라도 소수를 구하는 과정에 쓸데없는 과정이 더 생길 경우 시간 초과가 발생할 수도 있는 것 같다.
소수를 구하는 과정은 에라토스테네스의 체를 그대로 사용했다.
연속합을 구해주는 과정은 더블 포인터를 사용하지 않아도 해결할 수 있는 문제다.
그래서 처음에는 더블 포인터를 사용하지 않고 통과를 했었다.
소수들을 뒤에서부터 역순으로 검색한 이유는 소수간의 간격이 수가 커질수록 점점 커진다는 것을 이용해서 조금이나마 시간을 줄이기 위해서였다.
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
|
n = int(input())
num = [1] * (n+1)
for i in range(2, n+1):
if num[i]:
t = 2
while i * t <= n:
num[i * t] = 0
t += 1
ans = 0
for i in range(n, 1, -1):
if num[i]:
tmp = 0
for j in range(i, 1, -1):
if num[j]:
tmp += j
if tmp == n:
ans += 1
break
elif tmp > n:
break
print(ans)
|
더블 포인터를 이용한 코드는 아래와 같다.
2에 대한 예외처리가 안됐어서 한 번 틀렸었다...ㅎㅎ..
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
|
n = int(input())
num = [True] * (n+1)
num[0] = num[1] = False
for i in range(2, n + 1):
if num[i]:
t = 2
while i * t <= n:
num[i * t] = 0
t += 1
prime = sorted([i for i in range(2, n+1) if num[i]], reverse=True)
len_prime = len(prime)
ans = 0
if len_prime >= 1:
lo, hi, tmp = 0, 1, prime[0]
while lo < len_prime:
if tmp >= n:
if tmp == n:
ans += 1
tmp -= prime[lo]
lo += 1
# tmp < n
elif hi == len_prime:
break
else:
tmp += prime[hi]
hi += 1
print(ans)
|
잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다
728x90
'algorithm > 백준알고리즘' 카테고리의 다른 글
[백준알고리즘] 1208번: 부분수열의 합 2 -Python (0) | 2020.03.12 |
---|---|
[백준알고리즘] 1261번: 알고스팟 -Python (0) | 2020.03.12 |
[백준알고리즘] 1806번: 부분합 -Python (0) | 2020.03.11 |
[백준알고리즘] 2003번: 수들의 합 2 -Python (1) | 2020.03.11 |
[백준알고리즘] 1182번: 부분수열의 합 -Python (0) | 2020.03.11 |