2022. 10. 11. 14:16ㆍPS (Program Solving)/BOJ (백준)
문제 설명
https://www.acmicpc.net/problem/6588
접근 방법 - 에라토스테네스의 체 알고리즘을 응용한 소수 연산 문제
백준의 6588번 문제는 에라토스테네스의 체 알고리즘을 이용하여 구한 소수를 통해 연산해야 하는 문제이다.
해당 문제는, 각 케이스마다 주어지는 2보다 큰 짝수에 대하여 2개의 소수 합으로 나타내어 출력해야 하는 문제이다.
에라토스테네스의 체 알고리즘에 대한 설명은 이전 ps글에서도 다룬 적이 이미 있기 때문에 이 링크를 아래에 기재해놓았다.
또한, 이 문제와 유형은 똑같지만 난이도는 비교적 낮은 문제에 대한 풀이도 이전에 ps글에서 다루었기 때문에 이것도 함께 기재하였다.
해당 알고리즘이 어색하다면, 아래의 링크들을 한번 참고해보길 바란다.
https://smary-it.tistory.com/157
https://smary-it.tistory.com/231
여기서, 답이 여러 개인 경우엔 정답인 두 숫자의 차이가 가장 큰 것을 출력하라고 하니 이 점도 함께 참고해야 할 것이다.
혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.
필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.
코드의 실행 순서
1) 에라토스테네스의 체 알고리즘을 수행하기 위한 배열(arr)을 전역 변수로 선언해둔다.
2) 에라토스테네스의 체 알고리즘을 수행한다. (연산 방법을 알고 있다면 이 설명은 넘어가도 좋다.)
(이때, arr의 배열값이 0이라면 소수임을 뜻하며 1이라면 소수가 아님을 뜻한다고 가정한다.)
- 우선, 0과 1은 소수가 아니기 때문에 각 arr의 배열값을 1로 설정해둔다.
- 2부터 시작하여 자기 자신을 제외한 배수들을 인덱스로 갖는 배열값들은 모두 1로 설정해둔다.
자기 자신을 제외한 모든 소수의 배수들은 소수가 아니라는 점을 이용한 것이다.
3) 무한 반복문을 수행하여 아래의 연산을 취한다.
- 값(a)을 입력받는다. (여기서, 0을 입력받으면 해당 반복문을 종료한다.)
- 정답을 출력했는지에 대한 여부를 확인하기 위한 변수 cnt를 0으로 초기화하여 선언한다.
- 반복문을 통해 정답을 탐색한다. (필자 같은 경우에는, 시간 초과를 피하기 위해 반복문 하나로 정답을 탐색하였다.)
현재 탐색 중인 값(i)과 a/2에 대하여 대칭되는 값(a-i)이 둘 다 소수라면 이를 정답으로 출력한다.
(여기서, 이 반복문의 탐색법은 바깥쪽에서부터 a/2 중앙으로 폭을 좁혀오기 때문에, 이 반복문을 통하여 첫 번째로 발견된 정답이 두 숫자 간 격차가 가장 큰 경우이다. 따라서 즉시 정답으로 출력해야 한다.)
정답을 출력하였다면, cnt에 1을 더한 뒤 탐색을 멈추도록 한다.
- 만일 해당 케이스에 대한 정답이 출력되지 않았다면, cnt의 값도 그대로 0일 것이다. 따라서 이 경우엔 문제에 제시된 문자열을 출력하도록 한다.
4) 위 무한 반복문이 종료되었다면, 실행 종료한다.
성공한 코드
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;
//백준 6588번 코드
int arr[1000001];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
arr[0] = 1; arr[1] = 1;
for (int i = 2; i < 500001; i++) {
if (arr[i] == 1) { continue; }
for (int j = 2; i * j < 1000001; j++) {
arr[i * j] = 1;
}
}
while (1) {
int a;
cin >> a;
if (a == 0) { break; }
int cnt = 0;
for (int i = 3; i < a; i += 2) {
if (arr[i] == 0 && arr[a - i] == 0) {
cout << a << " = " << i << " + " << a - i << endl;
cnt++; break;
}
}
if (cnt == 0) {
cout << "Goldbach's conjecture is wrong.\n";
}
}
}
제출 결과
(2022.07.11 백준 6588번 문제 제출 결과)
'PS (Program Solving) > BOJ (백준)' 카테고리의 다른 글
[백준 BOJ] 17173번 배수들의 합 (C++/cpp) (0) | 2022.10.12 |
---|---|
[백준 BOJ] 22966번 가장 쉬운 문제를 찾는 문제 (C++/cpp) (0) | 2022.10.11 |
[백준 BOJ] 25206번 너의 평점은 (C++/cpp) (0) | 2022.10.11 |
[백준 BOJ] 3046번 R2 (C++/cpp) (0) | 2022.10.07 |
[백준 BOJ] 9020번 골드바흐의 추측 (C++/cpp) (0) | 2022.10.06 |