[백준 BOJ] 5618번 공약수 (C++/cpp)

문제 설명

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

5618번: 공약수

 

접근 방법 - 수학적 개념에 대한 연산 문제

백준의 5618번 문제는 공약수라는 수학적 기본 개념에 대해 묻고 있는 연산 문제이다.

해당 문제는, 2개 또는 3개의 입력값들에 대한 공약수들을 오름차순으로 출력해야 하는 문제이다.

여기서 공약수란, 주어진 정수들에 있어 공통되는 약수를 뜻한다.

따라서 주어진 입력값들에 대해 나누어 떨어지는 수들을 순차적으로 구할 수 있다면, 어렵지 않게 풀 수 있는 문제인 것이다.

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

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

 

코드의 실행 순서

1) 입력값의 개수(n)와 입력값들을 저장할 배열(arr)을 선언해둔다.

추가로, 입력값들 중 최솟값을 구하기 위해 min 변수를 선언해둔다. 입력값 범위 내의 최댓값으로 min을 초기화한다.

 

2) 입력값 개수(n)를 입력받는다.

 

3) n의 크기만큼 값들을 입력받는다. 그와 동시에 min 변수를 통해 최솟값도 함께 구한다.

 

4) 1은 모든 숫자의 약수이다. 따라서, 우선 1을 출력한다.

 

5) 2부터 min의 크기까지 반복문을 실행하며 아래의 연산을 취한다.

- n이 2인 경우, 입력값은 2개이다. 따라서, 2개의 입력값에 대해 현재 탐색값이 나누어 떨어지는 경우, 이 탐색값을 즉시 출력한다.

- n이 3인 경우, 입력값은 3개이다. 따라서, 3개의 입력값에 대해 현재 탐색값이 나누어 떨어지는 경우, 이 탐색값을 즉시 출력한다.

 

6) 4) ~ 5)의 과정으로 모든 공약수를 출력하였다면, 실행 종료한다.

반응형

 

성공한 코드

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

//백준 5618번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;	long long int arr[3];
	cin >> n;
	int min = 100000000;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (min > arr[i]) { min = arr[i]; }
	}
	cout << 1 << endl;
	for (int i = 2; i <= min; i++) {
		if (n == 2) {
			if (arr[0] % i == 0 && arr[1] % i == 0) {
				cout << i << endl;
			}
		}
		else if (n == 3) {
			if (arr[0] % i == 0 && arr[1] % i == 0 && arr[2] % i == 0) {
				cout << i << endl;
			}
		}
	}
}

 

제출 결과

(2022.05.02 백준 5618번 문제 제출 결과)

문제의 아래에 브루트포스 알고리즘 태그가 걸려있긴 했지만 사실상 그런 것 치곤 크게 어렵지 않았다..