링크 : https://www.acmicpc.net/problem/14476
문제 설명 :
정수 A가 B로 나누어 떨어지면, B는 A의 약수이고 A는 B의 배수이다.
최대공약수란 정수의 공통된 약수 중 가장 큰 수를 말한다. 예를 들어, 12와 8의 공통된 약수 1, 2, 4 중에서 가장 큰 것은 4이기 때문에 12와 8의 최대공약수는 4이다.
N개의 정수 중에서 임의의 수 K를 뺐을 때, 나머지 N-1개의 최대공약수가 가장 커지는 것을 찾는 프로그램을 작성하시오. 이때, 최대공약수는 K의 약수가 되면 안 된다.
예를 들어, 정수 8, 12, 24, 36, 48에서 8을 빼면 나머지 12, 24, 36, 48의 최대공약수는 12가 되고, 12는 빠진 수 8의 약수가 아니기 때문에 정답이 될 수 있다. 이때, 다른 수를 빼도 최대공약수가 8보다 커질 수 없다.
하지만, 8, 12, 20, 32, 36의 경우에는 그 무엇을 빼더라도 나머지 수의 최대공약수가 K의 약수가 되기 때문에, 정답을 구할 수 없다.
N개의 수가 주어졌을 때, 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 구하는 프로그램을 작성하시오.
입력 :
첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.
출력 :
첫째 줄에 정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수를 출력하고, 공백을 출력한 다음 뺀 수를 출력한다.
뺀 수를 K라고 했을 때, 나머지 수의 최대공약수가 K의 약수가 되면 안 된다.
만약 정답이 없는 경우에는 -1을 출력한다.
예제 입력 :
5
8 12 24 36 48
예제 출력 :
12 8
접근법 :
1) 어떻게 풀 것인가?
2) 시간복잡도
3) 공간복잡도
4) 풀면서 놓쳤던점
5) 이 문제를 통해 얻어갈 것
Java 코드 :
import java.io.*;
import java.util.*;
// 최대공약수 하나 빼기 14476
public class Main {
static int N, ans, ansId; // ans : 빼서 만들 수 있는 최대공약수, ansId : 제외할 숫자
static int[ ] inputArray;
static int[ ] L2R;
static int[ ] R2L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 1. 입력 받는다
N = Integer.parseInt(br.readLine());
inputArray = new int[N+1];
L2R = new int[N+1];
R2L = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i<N; i++) {
inputArray[i] = Integer.parseInt(st.nextToken());
}
// 2. 왼쪽에서 오른쪽으로 가면서 최대공약수 구하기
L2R[0] = inputArray[0];
for (int i = 1; i<N; i++) {
L2R[i] = getGcd(L2R[i-1], inputArray[i]);
}
// 3. 오른쪽에서 왼쪽으로 가면서 최대공약수 구하기
R2L[N-1] = inputArray[N-1];
for (int i = N-2; i >= 0; i--) {
R2L[i] = getGcd(inputArray[i], R2L[i+1]);
}
// 4. 최대공약수의 최댓값 구하기
int tmp;
ans = ansId = 0;
tmp = R2L[1];
if (inputArray[0] < tmp || getGcd(inputArray[0], tmp) != tmp) {
ans = tmp;
ansId = 0;
}
for (int i = 1; i < N-1; i++) {
tmp = getGcd(L2R[i - 1], R2L[i + 1]);
if ( inputArray[i] < tmp || getGcd(inputArray[i], tmp)!= tmp){
if (ans < tmp) {
ans = tmp;
ansId = i;
}
}
}
if (inputArray[N - 1] < L2R[N - 2] || getGcd(inputArray[N - 1], L2R[N - 2]) != tmp) {
if (ans < tmp) {
ans = L2R[N - 2];
ansId = N - 2;
}
}
if ( ans == 0 ) {
bw.write("-1");
}
else {
bw.write(ans+" "+inputArray[ansId]);
}
bw.flush();
bw.close();
br.close();
}
static int getGcd(int a, int b) {
int c;
while (b!=0) {
c = a%b;
a = b;
b = c;
}
return a;
}
}
C++ 코드 :
// 분수 합 14476
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#define MAX (1000000+3)
using namespace std;
int gcd(int a, int b) {
// a > b가 되도록 swap(a,b)
if (b > a) {
int tmp = b;
b = a;
a = tmp;
}
// 유클리드 호제법
int c;
while (b) {
c = a % b;
a = b;
b = c;
}
return a;
}
int arr[MAX];
int L2R[MAX];
int R2L[MAX];
int N;
int ans; // 빼서 만들 수 있는 가장 큰 최대공약수
int ansId; // 제외할 숫자
void input();
int main() {
// 1. 입력받는다
//freopen("input.txt", "r", stdin);
input();
// 2. 왼쪽에서 오른쪽으로 가면서 최대공약수 구하기
L2R[0] = arr[0];
for (int i = 1; i < N; i++) {
L2R[i] = gcd(L2R[i-1], arr[i]);
}
// 3. 오른쪽에서 왼쪽으로 가면서 최대공약수 구하기
R2L[N - 1] = arr[N - 1];
for (int i = N-2; i >= 0; i--) {
R2L[i] = gcd(arr[i], R2L[i+1]);
}
// 4. 최대공약수의 최댓값 구하기
int tmp;
ans = ansId = 0;
tmp = R2L[1];
if (arr[0] < tmp || gcd(arr[0], tmp) != tmp) {
ans = tmp;
ansId = 0;
}
for (int i = 1; i < N-1; i++) {
tmp = gcd(L2R[i - 1], R2L[i + 1]);
if ( arr[i] < tmp || gcd(arr[i], tmp)!= tmp){
if (ans < tmp) {
ans = tmp;
ansId = i;
}
}
}
if (arr[N - 1] < L2R[N - 2] || gcd(arr[N - 1], L2R[N - 2]) != tmp) {
if (ans < tmp) {
ans = L2R[N - 2];
ansId = N - 2;
}
}
// 3. 정답 출력
if (ans == 0) {
printf("%d", -1);
return 0;
}
printf("%d %d",ans, arr[ansId]);
return 0;
}
void input() {
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
}
#endif
'알고리즘 Algorithm > BOJ 백준 (초급~중급)' 카테고리의 다른 글
[BOJ 백준] 에라토스테네스의 체(2960) C++ (0) | 2023.01.12 |
---|---|
[BOJ 백준] 캔디 분배(3955) C++, Java (0) | 2023.01.12 |
[BOJ 백준] 분수 합(1735) C++, Java (0) | 2023.01.12 |
[BOJ 백준] 강수량(2094) C++ (0) | 2023.01.11 |
[BOJ 백준] 개똥벌레(3020) C++ (0) | 2023.01.11 |