백준 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과 같은 표현도 적합하지 않다.

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

 

 

---

처음 문제를 풀때 소수를 구하고 하나씩 더하면서 큰건 빼는 식으로 푸려고 하였다. 하지만 자꾸 틀렸습니다. 라고 뜨길래 찾다가 도무지 이해를 하지 못해 다른 사람의 알고리즘과 비교를 하였다. 결론적으로 말하면 문제는 소수를 구하는 알고리즘이 2,3,5,7로만 구하였는데 이것은 잘못된 방법이였고 나는 이 방식이 맞다고 생각하였기 때문에 틀린부분을 찾지 못한것이였다. 

다시 한번 느끼는 테스트의 소중함이다. 단순히 지레짐작으로 맞다 생각말고 여러번의 테스트로 확신을 가지자.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int result = 0;
int count1 = 0;
int n ,loop_count;
int storage[1000000];

int main(void) {
	
	scanf("%d", &n);
	vector check;
	check.resize(n + 1, true);
	for (int i = 2; i*i <= n; i++) {
		if (!check[i]) continue;
		for (int j = i * i; j <= n; j+=i) {
			check[j] = false;
		}
	}

	for (int i = 2; i <= n; i++) {
		if (check[i]) {
			storage[count1]=i;
			count1++;
		}
	}

	int sum=0, hi=0;
	int minus_count=0;
	int current_totalvalue=0;
	/*while (1) {
		loop_count++;
		if (sum >= n) sum -= storage[minus_count++];
		else if (hi == count1) break;
		else sum += storage[hi++];
		if (sum == n) result++;
	}*/

	for (int i = 0; i < count1; i++) {
		if (current_totalvalue < n) {
			loop_count++;
			current_totalvalue += storage[i];
		}
		else if (current_totalvalue == n) {
			loop_count++;
			result++;
			current_totalvalue += storage[i];
		}
		else {
			while (true) {
				if (minus_count + 2 == i) {
					loop_count++;
					if (storage[minus_count] + storage[i-2] > n) {
						if (storage[count1 - 1] == n) result++;
						printf("%d",result);
						return 0;
					}
				}
				if (current_totalvalue == n) {
					loop_count++;
					result++;
					current_totalvalue += storage[i];
					break;
				}
				else if (current_totalvalue < n) {
					loop_count++;
					current_totalvalue += storage[i];
					break;
				}
				loop_count++;
				current_totalvalue -= storage[minus_count];
				minus_count++;
			}
		}
	}
	if (storage[count1 - 1] == n) result++;
	printf("%d", result);
	return 0;
}

후기 및 느낀점 : 중간에 특정소수 + 특정소수가 찾고자 하는 소수의 합보다 크게 된다면 그 뒤는 더이상 탐색할 필요가 없다. 그래서 그러한 규칙을 적용해서 알고리즘을 돌렸더니 400만의 소수에서는 30만번의 반복횟수를 줄일수 있었다. 하지만 시간은 20ms로 차이가 없었고 이게 의미하는 바는 내부적으로 검사해야 할 if문이 더 많아서 그럴수도 있고 30만은 컴퓨터에 비해서 작은 연산이어서 그럴수도 있다. 오히려 가독성만 더 안좋아진것 같다. 물론 숫자가 엄청나게 커지면 효율성이 많이 증가하겠지만 백준과 같은 알고리즘에서는 그냥 특정 규칙만 찾아서 돌려도 충분히 해결이 가능한것 같다. 오히려 가독성을 신경써서 짧게 줄이는 편이 나을것 같다는 생각을 했다. 또한 나는 400만이면 소수는 200만 정도 되고 최악의 경우 200만 + 200만의 연산 즉 400만의 연산이 될거라 생각했지만 실제로는 65만 정도의 연산 뿐이였다. 이 정도면 어차피 신경쓰지 않아도 될것 같다.