[Problem] 백준 14941번 호기심

https://www.acmicpc.net/problem/14941

14941번: 호기심

 맨 처음 이 문제를 읽었을 땐, 엄청 쉬운 문제라고 생각했다. 하지만 풀다보니 시간초과로 도저히 풀리지 않았던 문제이다.

 

 알고리즘 공부를 시작한 지 어느정도 시간이 지나고 나서 다시 이 문제를 보니, 두 가지 알고리즘 기법만 알면 쉽게 풀 수 있다는 걸 깨달았다. 내가 생각하는 이 문제의 골자는 시간복잡도를 줄이는 것이다. 그것을 해결하기 위한 방법은 소수를 구할 때는 에라토네스 기법을, a부터 b까지의 소수의 합을 구할 때는 부분 합 기법을 사용하는 것이다.

---

에라토네스 기법

 에라토네스의 체라고도 한다. 큰 범위의 소수를 확인할 때 유용하다. 아래 링크에서 그림과 함께 C++ 코드도 설명되어있다. 참고하자.

https://www.geeksforgeeks.org/sieve-of-eratosthenes/

Sieve of Eratosthenes - GeeksforGeeks

---

부분 합 기법

 정렬된 배열에서 평균을 빠르게 구하는 데에 쓸 수 있는 기법이다. 나중에 따로 정리해서 올리도록 하자.

 

---

두 가지 기법을 알고 있다면 풀이의 나머지는 식은 죽 먹기이다. 

 1) 에라토네스의 체를 이용해서 범위(10^5)의 소수를 구한 다음

 2) 부분 합 기법을 이용해서 3A-B+3C-D ... 에 대한 부분 합을 구한다.

 3) 문제에서 입력받는 a와 b의 값으로 적당한 부분합[b]-부분합[a-1]를 출력하면 끝!