[백준 BOJ] 26162번 인공 원소 (C++/cpp)

문제 설명

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

26162번: 인공 원소

 

접근 방법 - 소수 판정에 대한 브루트포스 알고리즘 문제

백준의 26162번 문제는 소수 판정과 관련하여 브루트포스 알고리즘의 원리를 이용해 해결해야 하는 문제이다.

해당 문제는, 입력값으로 주어지는 원소 번호에 대해 특정 소수 2개의 합으로 나타낼 수 있는 번호인지를 구하여 출력해야 하는 문제이다.

필자는 소수 판정 문제에 주로 사용되는 에라토스테네스의 체 알고리즘을 주요로 이용하여 해당 문제를 해결하였다.

다만 브루트포스 알고리즘 문제인 것을 고려하더라도, 실행 시간을 줄이기 위해 반복문의 사용을 되도록 줄이는 방향으로 코드를 작성해 보았다.

에라토스테네스의 체 알고리즘을 처음 접해본다면, 아래에 있는 관련 링크를 참고해 보면 좋을 것이다.

https://smary-it.tistory.com/157

[백준 BOJ] 2960번 에라토스테네스의 체 (C++/cpp)

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 에라토스테네스의 체 알고리즘에 사용할 배열(arr)을 전역 변수로 선언해 둔다.

 

2) 아래와 같은 원리로 에라토스테네스의 체 알고리즘을 수행한다.

(배열값이 0이면 소수로, 1이라면 소수가 아닌 수로 취급하는 원리이다.)
- 우선 0과 1은 소수가 아니기 때문에 배열값을 1로 설정하여 배제해 둔다.
- 2부터 시작하여, 자기 자신을 제외한 배수들의 배열값은 1로 설정하여 소수에서 배제해 둔다.
(위 연산을 거치지 않은 숫자는 전역 변수로 선언해 둔 상태의 값인 0이 지속되기 때문에 소수로 취급된다.)

 

3) 테스트 케이스의 수(n)를 입력받는다.

 

4) n의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- 판별하고자 하는 원소 번호(num)를 입력받는다.

- 인공 원소인지를 판별하기 위한 변수(possible)를 0으로 초기화하여 선언한다.

- 2부터 시작하여 num 이전까지 반복문을 실행해 본다.

만일 현재 탐색값(i)과 num에 현재 탐색값을 뺀 값(num-i)을 각각 인덱스로 갖는 배열값이 모두 0이라면, 이는 인공 원소임을 의미한다. 따라서 이 경우엔, possible에 1을 더하고 해당 반복문을 즉시 종료한다.

(위의 2개 값을 합한 값은 결국 num이기 때문에, 이렇게 반복문의 사용 횟수를 줄이도록 하였다.)

 

5) 위 연산이 끝났다면, possible의 값에 따라 출력을 수행하도록 한다.

만일 possible의 값이 0 이상이라면, 이는 인공 원소임을 의미한다. 따라서 이 경우엔, "Yes"를 출력한다.

다만 위 조건을 만족하지 않는다면, 이는 인공 원소가 아님을 의미한다. 따라서 이 경우엔, "No"를 출력한다.

 

6) 모든 테스트 케이스가 수행되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 26162번 코드
int arr[150];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	arr[0] = 1;	arr[1] = 1;
	for (int i = 2; i < 150; i++) {
		for (int j = 2; i * j < 150; j++) {
			arr[i * j]++;
		}
	}

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		int possible = 0;
		for (int i = 2; i < num; i++) {
			if (arr[i] == 0 && arr[num - i] == 0) {
				possible++;
				break;
			}
		}

		if (possible > 0) { cout << "Yes" << endl; }
		else { cout << "No" << endl; }
	}
}

 

제출 결과

(2022.12.06 백준 26162번 문제 제출 결과)