알고리즘 (PS)/BOJ
[백준] 1644 - 소수의 연속합 (G3)
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 나는 투포인터를 안쓰고 풀었는데, 정해가 투포인터라서 놀랐다. 확실히 '어떤 정렬된 것들중 일부의 연속' 은 투포인터를 쓰기 좋다. 일단 이 문제가 골드3이라서 당연히 DP부터 의심했는데, DP가 아닌 풀이가 떠올라서 바로 구현했다. 내가 푼 풀이와 투포인터 풀이를 모두 적어보겠다. 이분탐색을 이용한 풀이 소수의 리스트 2, 3, 5, 7, 11, 13, ,,,, 가 있다고 하고 소수의 누적합 배열을 s 라고 해보자. (누적합 배열은 0부터 시작한다고 하자) 최적해가 되는 구간은 어떤 소수로 시작할 것이다. 2로 시..
