Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- XML주석
- 피보나치수열
- fibo
- opic
- 디피
- XML
- 다이나믹프로그래밍
- 주석
- 오픽노잼공부방법
- 오픽노잼
- 영어회화
- dp
- dynamicProgramming
- 오픽가격
- 이진탐색
- 안드로이드주석
- ㅂ
- stack 스택
- 탑다운
- 바텀업
- English
- 영어말하기
- 안드로이드
- 오픽
- 메모이제이션
- topdown
- 오픽점수잘받는방법
- 오픽공부법
- 이진탐색 #나무 자르기
Archives
RUBY
[백준] 소수의 연속합 본문
출처:: www.acmicpc.net/problem/1644
분류:: 에라토스테네스의 체, 투포인터
1. 문제 이해 및 해결과정
- n이 400만으로 일반적인 소수찾는 알고리즘으로 탐색이 안된다 -> 에라토스테네스의 체 이용해야한다. - 1. 에라토스테네스의 체로 가능한 소수를 찾고 - 2. 투포인터로 연속된 소수의 합 가능한 경우를 센다 |
cf)
에라토스테네스의 체 hiruby.tistory.com/463
2. 풀이방법
#소수의 연속합
#https://www.acmicpc.net/problem/1644
import sys
import math
sys.stdin = open("input.txt","r")
n=int(input())
arr=[True for _ in range(n+1)]
prime=[]
#2부터 n까지 중 가능한 소수 찾기
def isprime(n):
for i in range(2,int(math.sqrt(n))+1):
if arr[i]==True:
j=2
while i*j<=n:
arr[i*j]=False
j+=1
isprime(n)
for i in range(2,n+1):
if arr[i]:
prime.append(i)
#투포인터
s,e=0,0
sum=0
cnt=0
for s in range(len(prime)):
while e<len(prime) and sum<n: #합이 목표값보다 작고, 인덱스 이내라면
sum+=prime[e] #sum늘림
e+=1
if sum==n: #연속된 소수의 합이 n이라면
cnt+=1
sum-=prime[s]
print(cnt)
3. 오답원인
4. 알게된 점
'PS > BOJ' 카테고리의 다른 글
[백준] 로봇 청소기 | 삼성 (0) | 2020.09.20 |
---|---|
[백준] 부등호 (0) | 2020.09.18 |
[백준] 랜선자르기 (0) | 2020.09.17 |
[백준] 음악프로그램 (0) | 2020.09.17 |
[백준] 수들의 합2 (0) | 2020.09.17 |
Comments