728x90
시간 제한 | 메모리 제한 |
2 초 | 128 MB |
문제 (링크)
https://www.acmicpc.net/problem/1644
나의 풀이
import sys
import math
n = int(sys.stdin.readline())
# n이하의 수 중 소수를 찾아줄 배열 (에라토스테네스의 체)
prime_checker = [True for _ in range(n+1)]
# 소수가 아닌 0과 1에 대해 별도의 False처리
prime_checker[0:2] = False
for i in range(2, int(math.sqrt(n)) + 1):
if prime_checker[i]:
j = 2
while i * j <= n:
arr[i *j] = False
j += 1
# n이하의 소수값을 담아줄 배열
arr = []
for i in range(n+1):
if prime_checker[i]:
arr.append(i)
# arr에 대해서 투 포인터 알고리즘
end = 0
intervalSum = arr[0]
cnt = 0 # 경우의 수를 담아줄 변수
for start in range(len(arr)):
while intervalSum < n and end < len(arr):
end += 1
if end == len(arr):
break
intervalSum += arr[end]
if intervalSum == n:
cnt += 1
intervalSum -= arr[start]
print(cnt)
접근 방법 및 코드 설명
기존의 투 포인터 알고리즘(배열의 연속된 값)에 소수 값들에 대한 처리를 해줘야하는 에라토스테네스의 체 방식을 결합시켜야하는 방식이다.
입력 받은 n값에 대하여 2 ~ n까지의 모든 소수를 찾기 위해서 에라토스테네스의 체 방식을 사용해 걸러주고, 해당 소수를 arr라는 새로운 배열에 담아준다.
arr에 2 ~ n까지의 소수값들이 담기고 나면, 기존의 투 포인터 방식을 이용해 intervalSum값을 구해주고 해당 값이 입력값 n과 같다면 경우의 수를 세 주는 cnt 변수에 1을 더해주는 방식이다.
두 개의 알고리즘을 모두 알고 있다면 어렵지 않게 짤 수 있는 코드였다.
투 포인터 알고리즘 - seongonion.tistory.com/47?category=868991
소수 판별 알고리즘 - seongonion.tistory.com/43?category=868991
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준] 1874번 스택 수열 - 파이썬(Python) (0) | 2021.02.02 |
---|---|
[프로그래머스] Summer/Winter Coding(~2018) - 스킬트리 - 파이썬(Python) (0) | 2021.02.02 |
[백준] 1806번 부분합 - 파이썬(Python) (0) | 2021.02.02 |
[백준] 2003번 수들의 합2 - 파이썬(Python) (0) | 2021.02.01 |
[백준] 4948번 베르트랑 공준 - 파이썬(Python) (0) | 2021.01.31 |