백준 소수의 연속합 16441 [6개월 안에 백준 플래티넘 달성하기] 22. 소수의 연속합 소수의 연속합 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 풀이 문제를 처음 봤을 때는 DP풀이를 생각해 봤습니다. 하지만 규칙을 찾지 못하여 다른 풀이를 찾게 되었습니다. N의 수가 4,000,000으로 매우 크기 때문에 해당 범위 안에 있는 소수의 개수가 적을 경우 좀 더 다양한 풀이를 생각할 수 있다고 생각하여 에라토스테네스의 체를 이용하여 소수를 구해주었습니다. N이 4,000,000일 때 소수의 개수는 대략 20만 개로 여전히 n제곱의 알고리즘은 사용할 수 없었습니다. 그렇게 소수를 나열한 상태로 방법을 찾아봤습니다. 결국에는 연속된 수만 허용되기 때문에 투 포인터로 가능할 거 같았습니다. 0의 인덱스부터 합을.. 2024. 1. 10. 이전 1 다음 반응형
