[백준 29728] 실버와 소수는 둘다 S로 시작한다 (C++)

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

문제

---

브실이는 실버 난이도의 소수 관련 문제를 풀던 도중, "실버"와 "소수"가 동일하게 S로 시작한다는 것을 깨달았다.

물론 소수는 한글로 적었을 때의 발음만 S로 시작하지, 영어로는 prime이라 틀린 말이지만 브실이는 새로운 문제를 만들 생각에 들떠 세세한 것은 신경 쓰지 않기로 했다. 브실이가 구상한 문제는 다음과 같다.

먼저 빈 문자열 A를 준비한다. 그러면 브실이가 정수 N을 불러줄 것이다. 첫 번째 차례부터 N번째 차례까지 다음 작업을 진행한다.

1. 현재 차례가 소수 번째가 아닌 경우, A의 끝에 알파벳 B를 추가한다.
2. 현재 차례가 소수 번째인 경우는 조금 특별하다. 만약 A의 마지막 문자가 B인 경우 마지막 문자를 알파벳 S로 교체하고, A의 끝에 S를 하나 추가한다. 아니라면 단순히 A의 끝에 S를 하나 추가한다. 이후 A를 뒤집는다.

브실이는 이러한 문제를 구상했지만 N이 클수록 A도 엄청나게 길어질 텐데, 이러한 문자열을 일일이 채점할 자신이 없다. 따라서 S에 포함된 B와 S가 각각 몇 개인지를 기준으로 삼아 채점을 진행하려고 한다.

브실이가 채점에 참고할 수 있도록 위 문제의 답지 작성을 도와주자.

단, 이 문제에서 말하는 소수는 1과 자기 자신 이외의 약수가 존재하지 않는 1 이외의 양의 정수라고 생각하자.

입력

---

첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 5000000)

출력

---

문자열 A에 포함된 알파벳 B의 개수와 S의 개수를 공백으로 구분하여 출력한다.

 

문제 풀이

---

에라토스테네스의 체 + 자료구조 문제.

 

자연수 i가 소수인지 판별하기 위해 에라토스테네스의 체를 사용한다.

소수번째이면서 마지막 문자가 S인 경우, 문자열을 뒤집는다. N이 5000000이기 때문에 실제로 뒤집으면 시간이 오래 걸린다. 따라서 앞에서나 뒤에서나 삽입이 가능한 덱을 사용하여 문제를 해결한다. 문자열을 뒤집는 경우를 정방향 / 역방향 전환으로 생각하여, 처음 생성 시에는 push_back()을 이용한다. 이후 문자열을 뒤집게 되면 push_front()를 이용해 삽입하고, 다시 문자열을 뒤집게 되면 push_back()을 사용해주면 된다.

 

아래는 코드.

#include <iostream>
#include <deque>
#include <cmath>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	bool* isPrime = new bool[5000001];
	for (int i = 0; i < 5000001; i++)
	{
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i <= sqrt(5000000); i++)
	{
		for (int j = 2 * i; j < 5000001; j += i)
		{
			isPrime[j] = false;
		}
	}
	int N;
	deque<char> dq;
	bool isReverse = false;
	int B = 0;
	int S = 0;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		if (isPrime[i] == false)
		{
			if (isReverse == false)
			{
				dq.push_back('B');
				B++;
			}
			else
			{
				dq.push_front('B');
				B++;
			}
		}
		else if (isPrime[i] == true && isReverse == false)
		{
			char last = dq.back();
			if (last == 'B')
			{
				dq.pop_back();
				B--;
				dq.push_back('S');
				S++;
				dq.push_back('S');
				S++;
			}
			else
			{
				dq.push_back('S');
				S++;
				isReverse = true;
			}
		}
		else
		{
			char first = dq.front();
			if (first == 'B')
			{
				dq.pop_front();
				B--;
				dq.push_front('S');
				S++;
				dq.push_front('S');
				S++;
			}
			else
			{
				dq.push_front('S');
				S++;
				isReverse = false;
			}
		}
	}
	cout << B << " " << S << "\n";
	return 0;
}