✓

태그:

25. 투 포인터 CLASS 5

증가하는 수열의 연속한 원소의 합 비교는 변수 2개를 사용하면 $O(n)$입니다…!!

풀이 비스무리한거 보기

자연수가 주어졌을 때, 이를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다. 먼저 주어진 자연수 N까지의 소수를 모두 구합니다. 이를 순서대로 나열시킨 후, 두 인덱스 변수 x와 y를 첫 소수(2)에 위치시킵니다. 이 두 변수는 합을 나타내는 변수가 이 범위의 소수의 합임을 의미할 예정입니다(inclusive). 이제 합을 나타내는 변수를 2로 설정합니다. 그리고 N과 비교하면서 N보다 작다면 y를, N보다 크다면 x를, 같다면 카운트 변수와 x와 y 모두 1씩 증가시키는 과정을 구해놓은 소수의 범위를 넘어갈 때까지 진행하면 카운트 변수에 원하는 경우의 수가 저장됩니다. 이를 출력하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-06 16:04:01

---