[백준]1644번 - 소수의 연속합 -C/C++

 

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

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을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

---

에라토스테네스의 체를 활용하여 소수들의 합을 구한 다음 투 포인터로 푸는 문제이다.

처음에는 에라토스테네스의 체로 소수들을 구한 다음의 그 배열을 더해나가면서 부분합 배열로 바꾼 다음 부분합들 중 N과 일치하면 res를 증가시키는 방법을 사용하였으나 71%에서 틀렸습니다가 나왔다. 질문검색을 찾아보다 보니 부분합을 사용하여 문제를 푼 사람들은 시간 초과는 나지 않았지만 시간 초과 때문에 안된다는 것 같다고 했다.

그래서 투포인터로 문제를 풀었다.

문제를 풀고 보니 에라토스테네스의 체는 내가 생각한 방법으로 풀지 않고

for (int i = 2; i*i <= N; i++) {
		if (!check[i]) {
			for (int j = i*i; j <= N; j+=i) check[j] = true;
		}
	}
	
	for (int i = 2; i <= N; i++) {
		if (!check[i]) prime.push_back(i);
	}

와 같은 방법으로 푼다는 것을 알게 되었다. 이 방법의 시간 복잡도는 O(n*log(log(n)))이라고 한다.

#include <iostream>
#include <vector>

using namespace std;

int N;
vector <int> prime;
bool check[4000010] = { false };

int Eratos() {
	int res=0;
	for (int i = 2; i <= N; i++) {
		if (!check[i]) {
			prime.push_back(i);
			for (int j = 2; i * j <= N; j++) check[i*j] = true;
		}
	}
    
	int s = prime.size();
	int sum = 0, left = 0, right = 0;
	while (1) {
		if (sum >= N) {
			sum -= prime[left++];
		}
		else if (right == s) break;
		else {
			sum += prime[right++];
		}

		if (sum == N) {
			res++;
		}
	}
	return res;
}

int main() {
	cin >> N;
	cout << Eratos();
}

---

주말 내내 유튜브 클론 코딩만 했던 것 같다. 그래서 백준 문제는 되게 오랜만에 푸는 것 같았는데 부분합을 사용한 풀이가 왜 틀렸습니다가 나왔는지 알아내지 못해 뭔가 찝찝한 문제였다. 그래도 에라토스테네스의 체에 대해 다시 공부한 것 같아서 좋았다!

 

오늘은 SWEA 해설 특강을 들었다. 거기서는 카이스트 학부생인 코치님이 두 번째 강의를 해주셨다. 저번에도 되게 설명을 잘해주셔서 인상 깊었는데 이번에도 엄청나게 이해가 잘되게 설명을 해주셨다. 처음 봤을 때는 '와 학부생이 삼성 알고리즘 코치를?'이라는 생각이었는데 오늘 강의를 듣고 나서는 '저렇게 잘 가르치는 분이 삼성 알고리즘 코치를?'이라는 생각으로 바뀌게 되었다.

오늘 새롭게 알게된 테크닉이 되게 많았는데 너무 많이 감탄해서 마지막쯤에는 놀라는 게 식상하다는 생각을 했고 강의를 다 들으니 집중해서 들어서 인지 되게 피곤하였다. 같이 들은 친구와 같이 많은 것을 느낀 강의였던 것 같다. 이 풀이 방법은 한번 더 자세히 공부해봐야겠다!