[백준 BOJ] 27002번 Max Factor (C++/cpp)

문제 설명

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

 

 

접근 방법 - 소수 판정을 활용한 연산 문제

백준의 27002번 문제는 소수 판정의 원리를 활용하여 연산을 진행해야 하는 문제이다.

해당 문제는, 주어지는 일련번호들에 대해 가장 큰 소수 인수를 가지는 번호를 구하여 이를 출력해야 하는 문제이다.

(조건을 충족하는 정답이 2개 이상으로 나타나는 경우에는, 입력에서 가장 먼저 등장한 일련번호를 정답으로 출력하면 된다.)

문제의 게시판에 지문에 대한 번역본이 따로 없어, 생성형 AI를 통해 번역한 결과를 아래에 올리니 함께 참고하길 바란다.

 

필자는, 소수 판정과 연관성이 깊은 에라토스테네스의 체 알고리즘을 주로 활용하여 해당 문제 해결을 시도해 보았다.

만약 위 알고리즘에 대해 처음 접해본다면, 아래 문제의 해결을 우선 시도해 보거나 해설을 참고하면 도움이 될 것이다.

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

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

 

이 알고리즘을 활용하여 범위 내의 숫자들 중 소수를 모두 파악해 둔 뒤, 입력으로 주어지는 일련번호들에 대해 가장 큰 소수 인수를 각각 판별하고 이들을 비교해 가며 정답을 구하도록 하였다.

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

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

 

코드의 실행 순서

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

(일련번호로 주어지는 입력값의 최댓값이 20000이기 때문에, 1 ~ 20000 사이의 소수를 모두 파악하기 위해 배열의 크기 또한 20000으로 설정하였다.)

 

2) arr 배열에 대해, 에라토스테네스의 체 알고리즘을 수행한다.

(필자의 경우, 소수를 인덱스로 갖는 배열값은 0으로 하고 그 이외는 모두 1 이상의 값을 가지게끔 연산할 예정이다.)

- 0과 1은 소수가 아니기 때문에, 연산을 수행하기 전 arr[0], arr[1]의 값은 모두 1로 설정해 둔다.

- 2중 반복문을 활용하여, 각 제어 변수인 i와 j를 통하여 소수가 아닌 숫자들을 찾아내도록 한다.

i와 j를 각각 2부터 시작하고 1씩 증가한다는 전제 하에, i*j는 모두 소수라 보기 어렵다. 따라서 해당 숫자가 소수가 아니라는 점을 뜻하기 위해, arr[i*j]의 값에 각각 1을 추가하도록 한다.

(만약 arr[i]가 이미 0의 값을 유지하지 못하였다면, 모든 j에 대한 arr[i*j] 연산은 이미 이전에 끝났다고 볼 수 있다. 따라서 이 경우에는 continue를 통해 다음 루프의 연산을 수행하게끔 한다.)

 

3) 일련번호의 개수(t)를 입력받는다.

그리고, 일련번호의 값들을 저장할 벡터 v를 미리 선언해 둔다.

 

4) t의 크기만큼, 반복문을 수행하여 일련번호(num)를 하나씩 입력받는다.

num을 입력받을 때마다, 각 값을 v의 요소로 순차적으로 삽입하도록 한다.

 

5) 가장 큰 소수 인수를 저장할 변수 max를 0으로 초기화하여 미리 선언해 둔다.

이에 더불어, 가장 큰 소수 인수를 가지는 일련번호를 저장할 변수 result를 v[0] 값으로 초기화하여 미리 선언해 둔다.

(일련번호가 하나만 주어지는 경우에는 비교 연산을 수행할 필요가 없기 때문에, 우선은 v의 첫 번째 값으로 설정해 둔다. 일련번호가 2개 이상 주어지는 경우에는 비교를 수행하며 값을 갱신해 나갈 예정이다.)

 

6) t의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다.

- 현재 i번째 일련번호(v[i])에 대해 가장 큰 소수 인수를 임시로 저장할 변수 tmp를 0으로 초기화하여 미리 선언해 둔다.

- 다른 반복문을 통해, 2부터 v[i]까지 하여 순차적으로 소수 인수를 찾아보도록 한다.

v[i]를 나누었을 때 나누어 떨어지며 arr의 배열값이 0인 경우, 이 시점에서 해당 숫자는 v[i]에 대한 가장 큰 소수 인수라고 볼 수 있다. 이 경우에는, tmp의 값을 현재 j 값으로 갱신하도록 한다.

- 위 반복문 연산이 모두 완료되었다면, 현재의 tmp와 max 값을 비교해 본다.

만약 max보다 tmp의 값이 더 크다면, 지금까지 나온 소수 인수보다 더 큰 숫자가 나왔음을 의미하기 때문에 max를 tmp 값으로 갱신해 주고 result 값 또한 현재의 v[i] 값으로 갱신하도록 한다.

 

7) 6)의 연산을 모두 완료하였다면, 최종적으로 저장된 result의 값을 정답으로 출력한 뒤 실행을 종료한다.

반응형

 

성공한 코드

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

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

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

	int t;
	cin >> t;
	vector<int> v;
	for (int i = 0; i < t; i++) {
		int num;
		cin >> num;
		v.push_back(num);
	}

	int max = 0;
	int result = v[0];
	for (int i = 0; i < t; i++) {
		int tmp = 0;
		for (int j = 2; j <= v[i]; j++) {
			if (v[i] % j == 0 && arr[j] == 0) {
				tmp = j;
			}
		}

		if (tmp > max) {
			max = tmp;
			result = v[i];
		}
	}

	cout << result << endl;
}

 

제출 결과

(2025.09.29 백준 27002번 문제 제출 결과)