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

문제 링크

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

29728번: 실버와 소수는 둘다 S로 시작한다

 

문제

브실이는 실버 난이도의 소수 관련 문제를 풀던 도중, "실버"와 "소수"가 동일하게 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 ≤ 5,000,000)

 

출력

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

 

예제 입력 1

1

예제 출력 1

1 0

예제 입력 2

3

예제 출력 2

0 3

 

알고리즘 분류

• 자료 구조
• 소수 판정

 

풀이

빈 문자열 A는 덱을 사용해서 관리하면 된다.

문자열 A에 문자를 추가할 때는 먼저 덱의 back에서 원소를 push한다.

현재 차례가 소수 번째인 경우는 문자열을 추가하고, 이후부터는 덱의 front에서 원소를 push하도록 함으로써 문자열 A를 뒤집는다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <cmath>
#include <algorithm>
#define MAX 5000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int Prime[MAX];
deque<char> DQ;
bool isBack = false;
int B, S;

void input() {
    cin >> N;
}

void eratosthenes() {
    for (int i = 2; i <= N; i++) {
        Prime[i] = i;
    }
    for (int i = 2; i <= sqrt(N); i++) {
        if (Prime[i] == 0) {
            continue;
        }
        for (int j = (i * i); j <= N; j += i) {
            Prime[j] = 0;
        }
    }
}

void settings() {
    eratosthenes();
    for (int i = 1; i <= N; i++) {
        if (Prime[i] == 0) {
            if (isBack) {
                DQ.push_back('B');
            }
            else {
                DQ.push_front('B');
            }
        }
        else {
            if (isBack) {
                char Last = DQ.back();
                if (Last == 'B') {
                    DQ.pop_back();
                    DQ.push_back('S');
                }
                DQ.push_back('S');
            }
            else {
                char Last = DQ.front();
                if (Last == 'B') {
                    DQ.pop_front();
                    DQ.push_front('S');
                }
                DQ.push_front('S');
            }
            isBack = !isBack;
        }
    }
    while (!DQ.empty()) {
        char Now = DQ.front();
        if (Now == 'B') {
            B++;
        }
        else {
            S++;
        }
        DQ.pop_front();
    };
}

void find_Answer() {
    cout << B << " " << S << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}