문제
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
20
예제 출력 1
0풀이
🔥 문제 요약
연속된 소수들의 합으로 입력받은 숫자 N을 만드는 경우의 수를 출력한다.
🤔 생각해야 할 점
- 소수들은 연속해야 한다.
- 한 소수는 한번만 덧셈에 이용될 수 있다.
→ N까지의 소수를 전부 구해서 합이 N이 되는 부분 집합을 찾는다.
⇒ 투 포인터가 유리한 문제
- 부분 합의 시작과 끝을 나타내기 위해 start, end를 0번 인덱스로 초기화해서 사용
- start인덱스를 더했을 때 합이 N보다 작으면 start를 키워가며 더해준다.
- sum이 N보다 크다면 end 인덱스를 키워서 다 수를 더한 부분 합을 구한다.
🔥 풀이 과정
- sum이 N보다 작을 때: 부분합의 끝을 나타내는 end 인덱스의 값을 sum에 더해주고 인덱스를 이동한다.
- sum과 N이 같을 때 : answer++, start인덱스의 값을 빼고 인덱스 이동→ 다시 sum이 N보다 작은 값이 된다.
- sum이 N보다 클 때 : start인덱스 값을 sum에서 빼고 start인덱스를 이동 ( 부분합에 속하는 갯수가 줄어듬)
틀린 코드
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
bool isPrime(int num) {
if (num <= 1) //1은 소수가 아니니까
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)//나누어 떨어지는 수가 있으면 소수가 아니다.
return false;
}
return true;
}
int main() {
int N;
cin >> N;
for (int i = 2; i <= N; i++) {//2~N까지의 소수를 벡터에 저장
if (isPrime(i)) {//소수
v.push_back(i);
}
}
//투포인터
int start = 0;
int end = 0;
int sum = 0;
int answer = 0;
while (start <= v.size() && end <= v.size()){
if (sum < N) {//합이 주어진 소수보다 작으면
sum += v[end];//end인덱스의 값을 합에 더해줌
end++;
}
else if (sum > N) {//합이 주어진 소수보다 커지면
sum -= v[start];//start인덱스의 값을 합에서 빼고
start++;//start인덱스 이동
}
else if (sum == N) {//합과 소수가 같을 때
answer++;
sum -= v[start];
start++;//start의 값을 빼주니까 다시 주어진 소수보다 작은 상태가 된다.
}
}
cout << answer << endl;
return 0;
}- 소수를 구할 때 범위를 2~N까지 검사를 해야하는데 i의 범위를
i<N으로 설정해서 소수를 하나 빼고 구해서 계속 결과가 하나 모자라게 나왔다. - 벡터 범위 벗어나서 런타임 에러→ 뭐가 틀렸는데!!
🔥수정한 코드
#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
bool isPrime(int num) {
if (num <= 1) //1은 소수가 아니니까
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)//나누어 떨어지는 수가 있으면 소수가 아니다.
return false;
}
return true;
}
int main() {
int N;
cin >> N;
for (int i = 2; i <= N; i++) {//2~N까지의 소수를 벡터에 저장
if (isPrime(i)) {//소수
v.push_back(i);
}
}
//투포인터
int start = 0;
int end = 0;
int sum = 0;
int answer = 0;
while (start < v.size()){
if (sum < N) {//합이 주어진 소수보다 작으면
sum += v[end];//end인덱스의 값을 합에 더해줌
end++;
if(end > v.size())
break;
}
else if (sum > N) {//합이 주어진 소수보다 커지면
sum -= v[start];//start인덱스의 값을 합에서 빼고
start++;//start인덱스 이동
}
else if (sum == N) {//합과 소수가 같을 때
answer++;
sum -= v[start];
start++;//start의 값을 빼주니까 다시 주어진 소수보다 작은 상태가 된다.
}
}
cout << answer << endl;
return 0;
}✅ 소수를 구하는 함수
bool isPrime(int num) {
if (num <= 1) //1은 소수가 아니니까
return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0)//나누어 떨어지는 수가 있으면 소수가 아니다.
return false;
}
return true;
}✅ 2~N까지의 수를 검사해 그 중 소수를 v벡터에 넣는다.
for (int i = 2; i <= N; i++) {//2~N까지의 소수를 벡터에 저장
if (isPrime(i)) {//소수
v.push_back(i);✅ 연속하는 소수의 합이 N이 되는 것을 찾기 위해 2개의 포인터를 설정해 합을 구한다.
while (start < v.size()){
if (sum < N) {//합이 주어진 소수보다 작으면
sum += v[end];//end인덱스의 값을 합에 더해줌
end++;
if(end > v.size())
break;
}
else if (sum > N) {//합이 주어진 소수보다 커지면
sum -= v[start];//start인덱스의 값을 합에서 빼고
start++;//start인덱스 이동
}
else if (sum == N) {//합과 소수가 같을 때
answer++;
sum -= v[start];
start++;//start의 값을 빼주니까 다시 주어진 소수보다 작은 상태가 된다.
}
}🔥 어려웠던 점
while의 범위를 설정하는것, 반복문의 종단 조건 설정에 어려움이 있었다. 투포인터는 비슷한 문제를 여러번 계속 풀다보니까 금방 생각이 났는데 범위 설정이 힘들었다.
처음엔 반복문의 조건을 while (start <= v.size() && end <= v.size()) 이렇게 설정했는데 이렇게 되면 v.size()의 범위를 벗어나게 되어 런타임 에러가 발생한다. 하지만 그렇다고 while문의 조건을 end < v.size()로 설정하면 반복문이 완전히 돌지 않아서 그런지 경우의 수에서 계속 1이 빠진 값이 나왔다.
start < v.size() 만 설정하면 end가 범위를 벗어나게 되어 런타임 에러가 발생했기 때문에 결국에는 start < v.size()를 while문의 조건으로 설정하고 end를 증가시키는 if문에 따로 end > v.size()의 조건을 추가해서 end가 범위를 벗어나면 while문을 빠져나가도록 했다.
아오~~
++ 멘토링 후 추가
while의 범위 설정
- end 인덱스의 조건을 if문으로 따로 적어줘야하는 이유:
end 인덱스가 v벡터의 범위를 벗어났을 때 while 조건에 해당 조건을 넣으면 범위를 벗어나고도 다음 else if 문이 실행되면 안되기 때문에 범위를 벗어나면 즉시 끝낼 수 있도록 조건을 넣어준다. - end 인덱스의 범위가 if(end >= v.size()) 가 아닌 if(end > v.size()) 인 이유
sum에 값을 더하고 인덱스를 올리기 때문에 end인덱스가 v 벡터의 끝에 도달하고도 해당 인덱스를 포함한 start인덱스 이동의 결과로 나오는 sum의 결과도 확인해야하기 때문에 end의 종단은 v.size()의 마지막 인덱스까지가 아닌 그 다음 인덱스에 접근했을 때이기 때문에 >를 사용한다. + 위에서 말했듯이 v.size()+1인덱스에 도달하면 조건문으로 바로 반복을 중단해준다.
또 다른 해결 방법
아라토스테네스의 체
내가 코드에서 쓴 소수를 구하는 코드는 2~N의 모든 소수를 구하면서 2~n의 제곱근까지 모든 값에 대해 나누어 떨어지는지 검사한다. 근데 이 코드는 시간이 오래 걸리는 비효율적인 코드라는 것을 알게 되었다.
⭐️아라토스테네스의 체를 사용해서 코드를 작성하면 더 효율적으로 빠른 시간안에 해결할 수 있다.
- 2부터 시작해서 n까지 진행한다.
- 가장 작은 수를 선택한다.
- 그 작은 수를 소수라고 가정하고 작은 수부터 n까지 그 작은 수의 배수를 모두 제거한다.
for (int i = 2; i < N; i++){
if (check[i] == false){//i번째 인덱스가 소수라면
for (int j = i + i; j <= N; j += i){//i의 배수들은
check[j] = true;//소수가 아니다.
}
}
}확인을 안한거면 소수이다.
예를 들어 i인덱스에서 2가 소수임을 알게 되면 2의 배수들 (2, 4, 6,...)은 소수가 아니다.
->체에 거르듯이 걸러지게 된다.
