투포인터
-
[BOJ] 1644 소수의 연속합PS/BOJ 2020. 7. 16. 16:43
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 (두 www.acmicpc.net 알고리즘: 투포인터, 에라토스테네스의 체 시간복잡도: O(N*log(logN)) 접근: 1. 소수 판별 2. 연속된 합, N 제한( 1번은 에라토스테네스의 체를 이용하면 O(NloglogN) 만에 해결이 가능하다. 문제는 2번인데, 구간 합 문제라고 생각하고 i~j까지 모든 조합을 계산하면, O(N^2)으로 TLE를 받게 ..