[백준 BOJ] 11502번 세 개의 소수 문제 (C++/cpp)

문제 설명

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

11502번: 세 개의 소수 문제

 

접근 방법 - 에라토스테네스의 체를 활용한 브루트포스 알고리즘 문제

백준의 11502번 문제는 에라토스테네스의 체 알고리즘과 브루트포스 알고리즘을 함께 활용하여 해결해야 하는 문제이다.

해당 문제는, 입력받은 숫자에 대한 3개의 소수의 합을 오름차순으로 나타내어 출력해야 하는 문제이다.

2개의 알고리즘에 대해 능숙하게 활용할 수 있다면 크게 어렵지 않은 문제일 것으로 예상된다.

여기서, 브루트포스 알고리즘이란 모든 경우의 수를 시도해보며 정답을 탐색하는 알고리즘을 뜻한다.

에라토스테네스의 체 알고리즘은 소수를 구하는 알고리즘 중 하나인데 이에 대한 자세한 설명은 아래를 참고해보길 바란다.

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

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

혹여나 이 2가지의 알고리즘이 어색하다면 위 링크와 아래의 설명을 함께 참고해보길 바란다.

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

 

코드의 실행 순서

1) 에라토스테네스의 체 알고리즘을 수행하기 위한 배열(arr)을 전역변수로 선언해둔다.

 

2) 입력을 받기 전, 에라토스테네스의 체 알고리즘을 수행한다.

(0과 1은 소수가 아니니 배제, 소수에 대해 자기 자신을 제외한 배수들은 소수가 아니라는 점을 이용하여 알고리즘 수행)

(이에 대한 자세한 설명은 위 링크의 코드 설명 참고 바람)

 

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

 

4) n의 크기만큼 아래의 연산을 취한다.

- 연산을 수행할 값(num)을 하나씩 입력받는다.

- 연산 가능 여부를 나타내는 변수 cnt를 0으로 초기화하여 선언한다.

- 3개의 소수를 저장할 배열 a도 모두 0으로 초기화하여 선언한다.

- 3중 반복문을 이용하여 3개의 소수를 추려낸다.

(해당 탐색값들을 인덱스로 갖는 arr의 배열값이 0이어야 소수라 판단하기 때문에 중간마다 이에 대한 조건문을 실행한다.)

3개의 합이 num과 같다면, 연산이 성공했다는 의미로 cnt에 1을 더하고 a에 저장된 탐색값들을 정렬한 뒤 즉시 출력한다.

연산이 완료됐다면 cnt의 값을 이용한 조건문을 통해 모든 반복문을 탈출한다.

 

5) 연산이 성공하였다면 즉시 실행 종료하고, 만일 연산이 실패하였다면 0을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

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

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

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

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

		int cnt = 0;
		int a[3] = { 0 };
		for (a[0] = 2; a[0] < 1000; a[0]++) {
			if (arr[a[0]] > 0) { continue; }
			for (a[1] = 2; a[1] < 1000; a[1]++) {
				if (arr[a[1]] > 0) { continue; }
				for (a[2] = 2; a[2] < 1000; a[2]++) {
					if (arr[a[2]] > 0) { continue; }
					if (a[0] + a[1] + a[2] == num) {
						cnt++;
						sort(a, a + 3);
						for (int k = 0; k < 3; k++) {
							cout << a[k] << " ";
						}
						cout << endl;
					}
				}
				if (cnt > 0) { break; }
			}
			if (cnt > 0) { break; }
		}
		if (cnt == 0) { cout << 0 << endl; }
	}
}

 

제출 결과

(2022.05.09 백준 11502번 문제 제출 결과)