[백준/7512] 연속하는 소수의 합

1. 문제

1) 문제 링크

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

7512번: 연속하는 소수의 합

 

2) 설명

숫자 n_i들이 주어지면 각각 n_i 개만큼의 연속된 소수들의 합으로 만들 수 있는 최소의 소수를 구하는 문제다.

2. 풀이

1) 알고리즘

    : 에라토스테네스의 체, 슬라이딩 윈도우

 

2) 풀이 설명

 

일단 에라토스테네스의 체로 소수 배열(primes)을 구한다. 그리고 소수인지 아닌지 판별할 수 있는 isPrime배열까지채워넣는다.

사실 소수 구하는 코드는 기억을 더듬어 대강 한 거라 다른 풀이를 보는 게 더 나을 수도 있다.

 

이제부터 슬라이딩 윈도우로 문제를 풀면 된다.

먼저 각 케이스별로 구하는 답을 answer라고 한다.

 

이제 sumArray와 sumBeginIndex 배열을 이용해서 answer를 구해본다.

 

nArray[i] = 연속한 소수의 수

sumArray[i] = n_i개의 연속된 소수의 합으로 만든 소수

sumBeginIndex[i] = sumArray[i]의 소수를 만드는 연속된 소수들 중 첫번째 인덱스를 가리킨다.

 

예를 들어 nArray[i]가 3이면 sumArray와 sumBeginIndex에 가능한 값은 다음과 같다.

sumBeginIndex[3]	0	1	2
sumArray[3]	9 ( = 2 + 3 + 5 ) 근데 소수가 아니라 안 됨	15 ( = 3 + 5 + 7 ) 얘도 소수가 아니라 안 됨	23 ( = 5 + 7 + 11) 은 소수니까 ok

sumBeginIndex[3]에는 0, 1은 들어갈 수 없고 2부터 시작하게 된다.(소수 연속합이 소수여야 하므로)

 

그러면 그러면 이제 n_i별로 sumArray, sumBeginIndex를 구성할 수 있다.

 

첫 초기값을 구하고 슬라이딩 윈도우를 통해 계속 sumArray의 모든 원소가 answer와 같아질 떄까지 슬라이딩 + answer를 업데이트 해주면 된다.

 

이때 sumArray[i] < answer라면, sumArray[i[ 를 슬라이딩시킨다.(그 합이 소수가 될 때까지)

만약 sumArray[i] > answer라면, 더이상 해당 answer 값은 모든 n_i 개의 연속합으로 만든 공통의 소수가 될 수 없다... i개의 연속합으로 answer를 만들 수 없다는 말이기 때문이다..

 

앞서 말했듯 이런 식으로 sumArray와 sumBeginIndex, answer 값을 sumArray의 모든 값과 answer 값이 같아질 때까지 반복하면 된다!

 

 

3. 코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>

#define MAX_VAL 10000000

using namespace std;

vector<bool> isPrime(MAX_VAL, true); // 해당 수가 소수인지르 나타내는 배열
vector<int> primes; // 소수만 있는 배열

// 에라토스테네스의 체로 소수 구하는 함수
void setPrimes(){	
	isPrime[0] = isPrime[1] = false;
	isPrime[2] = true;
	for(int i=2;i<MAX_VAL;i++){
		if(isPrime[i] == false)
			continue;
		
		primes.push_back(i);
		
		for(int j=i*2;j<MAX_VAL;j+=i){
			isPrime[j] = false;
		}
	}
}

// 모든 sumArray가 같은 값을 갖고 있는지 확인
bool isCorrect(vector<int> sumArray, int val){
	for(auto x : sumArray)
		if(x != val)
			return false;
	return true;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	setPrimes();

	int t;
	cin >> t;
	for(int i=1;i<=t;i++){
		int m;
		cin >> m;
		vector<int> nArray(m, 0); // n_i 배열
		vector<int> sumArray(m, 0); // n_i만큼 연속된 소수의 합을 가진 배열(중요!! : 이 값은 소수여야 함)
		vector<int> sumBeginIndex(m, 0); // sumArray에 있는 연속된 소수의 합이 어디서부터 시작했는지를 가리키는 index의 배열

		//input
		for(int j=0;j<m;j++)
			cin >> nArray[j];

		//첫 sumArray와 sumBeginIndex 구하기
		for(int j=0;j<m;j++){
			sumArray[j] = accumulate(&primes[0], &primes[nArray[j]], 0);
			while(!isPrime[sumArray[j]]){ //구한 합이 소수인지 체크
				//소수가 아니라면 슬라이딩 윈도우로 증가
				sumArray[j] += primes[sumBeginIndex[j] + nArray[j]] - primes[sumBeginIndex[j]];//슬라이딩 윈도우로 다읍 값 더하고 맨 앞의 값 빼기 
				sumBeginIndex[j]++; //시작 인덱스 증가
			}
		}

		int answer = *max_element(sumArray.begin(), sumArray.end()); // answer 초기값 설정, 아마 min_element로 하든 뭐로 하든 sumArray 안의 값으로 하면 상관 없을 것 같다(어차피 아래 while문 통해서 업데이트 될 거라)
		
		while(!isCorrect(sumArray, answer)){ //sumArray 배열의 모든 값이 answer랑 똑같다면 정답을 구한 거임
			for(int j=0;j<m;j++){
				if(sumArray[j] < answer){
					//sumArray[j] 값이 answer보다 작으면 슬라이딩 윈도우로 beg ~ end -> beg+1 ~ end+1로 합 증가
					//이걸 새로 구한 소수의 연속합이 소수가 될 때까지 반복
					//초기값 구할 때와 달리 do while문인 이유는 얘는 이미 소수의 연속합이 answer보다 작기 때문에 최소한 한 번은 무조건 업데이트를 해줘야 하기 때문이다. 주석처리된 코드처럼 sumArray[j] += ~~~~~~; while(!isPrime[sumArray[j]]){~~~}로 해도 되지만 슬라이딩 윈도우하는 코드가 중복돼서 그냥 do while문으로 해줬다
					/*
					sumArray[j] += primes[sumBeginIndex[j] + nArray[j]] - primes[sumBeginIndex[j]];		
					sumBeginIndex[j]++;
					while(!isPrime[sumArray[j]]){
						sumArray[j] += primes[sumBeginIndex[j] + nArray[j]] - primes[sumBeginIndex[j]];		
						sumBeginIndex[j]++;
					}
					*/
					do {
						sumArray[j] += primes[sumBeginIndex[j] + nArray[j]] - primes[sumBeginIndex[j]];
						sumBeginIndex[j]++;
					} while(!isPrime[sumArray[j]]);
				} else {
					//sumArray 중에 answer보다 큰 값이 있으면 answer 값 업데이트
					answer = sumArray[j];
				}
			}
		}
		cout << "Scenario " << i << ":\n";
		cout << answer << "\n\n";
	}
	return 0;
}

 

 

4. 느낀점

개인적으로 소수 문제는 별로 선호하지 않는다.. (어렵기 때문 ㅎㅎ)

그래도 머리 싸매고 풀어내니까 기분이 좋더라..

근데 정작 내가 푼 알고리즘을 설명을 못 하겠다..

너무 복잡하게 푼 게 아닐까 싶어서 맞은 분들의 다른 풀이를 봤는데... 잘 모르겠더라..ㅎㅎㅎ

많이 부족함을 느낀다..