[BOJ] 1644 소수의 연속합 (C/C++)

1644번: 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

• 3 : 3 (한 가지)
• 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
• 53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

투 포인터 연습용으로 한 문제 더 풀어봤다. 예전에도 이런 부분합 문제를 풀어본 적이 있는 것 같은데 그때는 딱히 투 포인터에 신경 안 썼던 것 같다. 저번 문제는 두 포인터의 방향이 서로 반대였는데 이번엔 두 포인터 둘 다 오른쪽을 향하는 문제였다. 

 

에라토스테네스의 체를 많이 들어보긴 했는데 구현해본 적이 없어서 찾아봐야 했다. 아마 1학년 때에 한번쯤은 했을 것 같은데 기억이 전혀 안 난다.

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위키에 있는 애니메이션을 보고나서 에라토스테네스씨 이름이 지금까지 내려오는 데에는 다 이유가 있다고 생각했다. 히트다 히트. 아무튼 이 문제는 에라토스테네스의 체를 이용해서 N까지의 소수를 미리 구한다. 최대 소수 개수는 구할 수 있지만 배열 사이즈 잡기 귀찮아서 그냥 vector를 사용했다.

 

소수의 개수를 미리 다 구한 이후에 포인터를 모두 0번 인덱스에서 시작한다. 부분합을 구해가면서 조건에 따라서 포인터를 이동한다. 이때 while에 right < size라고 조건을 넣었다가 계속 답이 안 나왔는데 그 이유가 right가 N에 도달한 이후에도 left를 올리면서 부분합을 확인해야 되는데 while문을 그냥 튀어나가 버렸다. 그 조건을 while문 안에서 처리하니까 답이 나왔다.

 

후기)

투 포인터라고 이름이 붙어서 뭔가 하나의 방법이 있다기보단 포인터 두개 쓰면 투 포인터구나...