[BOJ 백준] 최대공약수 하나 빼기(14476) C++, Java

 

링크 : https://www.acmicpc.net/problem/14476

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