[백준 / BOJ] 1644 소수의 연속합

문제

출처 : www.acmicpc.net/problem/1644

1644번: 소수의 연속합

자연수 N이 주어진다.

연속된 소수들을 더해서 자연수 N을 더하는 경우의수를 구하는 문제다.

 

풀이

'연속된 소수들을 이용해서 N을 만들어야 한다'는 조건이 있기때문에, 투포인터를 이용해 풀수있다.

 

소수만을 가지고 N을 만들어야 한다. 매번 해당 숫자가 소수인지 판단하면 너무 오래걸리기 때문에, 에라스토테네스의 체를 이용해 미리 소수들을 구해서 벡터에 넣어줬다.

 

연속된 소수들의 시작idx와 끝idx를 나타내는 left, right를 선언해줬다.

연속된 소수들의 합 S = (vec[left] + vec[left + 1] + vec[left + 2] ... + vec[right - 2] + vec[right - 1] + vec[right])

 

1. S가 N보다 작다면, right를 늘려가며 S의 값을 늘린다.

 

2. S가 N과 같다면, left를 늘려가며 S의 값을 줄인다.

 

3. S가 N보다 작거나 같다면 left를 늘려가며 S의 값을 줄인다.

(작거나 '같다면'으로 선언하지않으면 구현방식에따라서 무한루프에 돌수도있다. 항상 같다고 판단해서 수의 변화 없이 계속 반복하게됨)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1644%20%EC%86%8C%EC%88%98%EC%9D%98%20%EC%97%B0%EC%86%8D%ED%95%A9/main.cpp

devxb/JJUNalgo