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

문제

1644번: 소수의 연속합

---

1. 마지막 풀이

사고 과정

연속된 소수의 합으로 표현하기?

 

배열에서 시작과 끝 인덱스를 지정해두고, 다 더한 게 n보다 작으면 끝을 한 칸 이동, n보다 크면 시작을 오른쪽으로 한 칸 이동.

 

2-Sum 알고리즘이 작동하듯 움직이면 될 것 같았다.

 

그런데 경우의 수를 세는 문제네? 그럼 찾았을 때 출력 대신 count를 증가시키고, 시작 인덱스를 옮기며 다시 진행하자.

 

탈출 조건을 정해줘야 한다. 시작 인덱스가 끝 인덱스를 넘어가면 끝나지 않을까?

 

그럼 이제 필요한 건 소수만 모아둔 배열. 이전 뻘짓 땐 노가다로 했었는데, 이번엔 에라토스테네스의 체로 만들어 보자.

매우 효율적이었던 체

 

[Algorithm] 에라토스테네스의 체

구현엔 이 분의 포스트를 참고해, 조금 더 효율적으로 개선했다.

 

이렇게 만들거면 소수 배열의 크기도 n까지만 하면 되겠네? 무조건 4,000,000 하는 거보단 수가 작을 때 효율적이겠다.

 

1. 에라토스테네스의 체 사용, 소수 배열 생성
2. start와 end 인덱스를 2로 선언
3. start 이상 end 이하 모든 소수를 더한 값을 sum이라고 할 때, 아래 알고리즘에 따라 이동
   1. sum == n일 경우, count를 1 증가시키고 start를 한 칸 이동
   2. sum < n인 경우, 더 더해야 하니 end를 한 칸 이동
   3. sum > n인 경우, 숫자를 빼야 하니 start를 한 칸 이동
4. start, end가 배열 범위를 벗어나거나, start가 end를 넘어가면 종료

 

코드

#include <iostream>
#include <vector>

std::vector<bool> is_prime;

void eratosthenes() {
	for (int i = 2; i < is_prime.size(); i++) {
		if (is_prime[i] == false) {
			continue;
		}

		for (int j = i * 2; j < is_prime.size(); j += i) {
			is_prime[j] = false;
		}
	}
}

// 답 확인 용
void print_nums(int start, int end) {
	for (int i = start; i <= end; i++) {
		if (is_prime[i] == true) {
			std::cout << i << " ";
		}
	}

	std::cout << "\n";
}

int main() {
	// 입력
	int n;
	std::cin >> n;

	is_prime.assign(n + 1, true);
	// 에라토스테네스의 체 생성
	eratosthenes();

	int start = 2, end = 2;
 	int sum = 2, count = 0;
	
	while (start < is_prime.size() && end < is_prime.size() && start <= end) {
		if (sum == n) {
;			count++;
			// sum에서 start를 빼고 start를1 증가
			sum -= start++;

			// 다음 소수로 이동
			while (start < is_prime.size() && is_prime[start] == false) {
				start++;
			}
		}

		else if (sum < n) {
			end++;
			// 다음 소수로 이동
			while (end < is_prime.size() && is_prime[end] == false) {
				end++;
			}
			sum += end;
		}

		else if (sum > n) {
			sum -= start++;

			// 다음 소수로 이동
			while (start < is_prime.size() && is_prime[start] == false) {
				start++;
			}
		}
	}

	std::cout << count;
}

 

결과

이게 되네

---

2. 개선

사고 과정

정답을 맞췄으니, 이제 코드를 읽기 쉽게 고쳐보자.

 

우선 다음 소수로 이동하는 로직은 함수화하면 가독성이 올라갈 것 같다.

 

// 다음 소수를 반환, 배열 범위 초과 시 size 반환
int moveToNextPrime(int i) {
	for (i++; i < is_prime.size(); i++) {
		if (is_prime[i] == true) {
			break;
		}
	}

	return i;
}

 

이렇게 코드를 분리해줬다.

 

while문의 순서를 바꾸면, 이 부분도 통합이 가능해 보였다.

 

	while (start < is_prime.size() && end < is_prime.size() && start <= end) {
		if (sum < n) {
			end = moveToNextPrime(end);
			sum += end;

			continue;
		}
		
		if (sum == n) {
;			count++;
		}

		sum -= start;
		start = moveToNextPrime(start);
	}

 

다만, 기존 코드보다 가독성이 뛰어난가?를 묻는다면 글쎄. 코드 해석은 더 어려워진 것 같다.

 

그래서 기존 방식으로 회귀했다.

 

else 대신 else if로 굳이 표현한 것도 가독성을 위함이었다.

 

코드

#include <iostream>
#include <vector>

std::vector<bool> is_prime;

void eratosthenes() {
	for (int i = 2; i < is_prime.size(); i++) {
		if (is_prime[i] == false) {
			continue;
		}

		for (int j = i * 2; j < is_prime.size(); j += i) {
			is_prime[j] = false;
		}
	}
}

// 다음 소수를 반환, 배열 범위 초과 시 size 반환
int moveToNextPrime(int i) {
	for (i++; i < is_prime.size(); i++) {
		if (is_prime[i] == true) {
			break;
		}
	}

	return i;
}

int main() {
	// 입력
	int n;
	std::cin >> n;

	is_prime.assign(n + 1, true);
	// 에라토스테네스의 체 생성
	eratosthenes();

	int start = 2, end = 2;
 	int sum = 2, count = 0;
	
	while (start < is_prime.size() && end < is_prime.size() && start <= end) {
		if (sum == n) {
;			count++;

			sum -= start;
			start = moveToNextPrime(start);
		}

		else if (sum < n) {
			end = moveToNextPrime(end);
			sum += end;
		}

		else if (sum > n) {
			sum -= start;
			start = moveToNextPrime(start);
		}
	}

	std::cout << count;
}

 

결과

 

함수로 뺀 만큼 시간은 늦춰졌지만, 이게 더 맘에 든다. 읽기도 쉽고.

---

가장 효율적인 코드

https://www.acmicpc.net/source/8705431

joeyvalentine님의 코드. 생각해보니 링크 탄다고 안 보이겠지만, 어쨌든...

상당히 암호같은 코드여서 동작 원리를 파악하는 게 중요해보인다. 나중에 공부해서 수정해야지.

---

강평

구현 자체는 어렵지 않았고, 다른 분의 코드 역시 같은 알고리즘을 사용했다. 다만 소수 판정이나 체 만들기에서 다른 점이 있어, 공부할 수 있었던 문제.