[코테] 백준 14476번 : 최대공약수 하나 빼기 (java)

 

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

 

알고리즘 분류 : 수학, 정수론, 누적합, 유클리드 호제법

❓문제

 

---

🔅해석

위 문제는 누적합과 유클리드 호제법을 이용하여 풀이해야한다.

 

먼저 두 수의 최대공약수를 구하는 방법인 유클리드 호제법을 구현한 코드이다.

// gcd(a, b) == gcd(b, r) : r = a % b
static int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

 

이 유클리드 호제법을 통해 나온 최대공약수를 누적합 배열에 담는다.

 

8 12 24 36 48

예를들어, 입력이 위와 같이 들어왔을 때, 8 ~ 48의 최대공약수는 gcd((((8,12), 24), 36), 48) 이 될 것이다.

여기서 24를 빼고 최대공약수를 구한다고 했을 때는 gcd(gcd(8, 12), gcd(36, 48)) 이 된다.

누적합 배열을 왼쪽에서 오른쪽, 오른쪽에서 왼쪽 방향으로 2가지 배열을 만들어 동일한 최대공약수 구하는 작업을 줄일 수 있다.

gcd(gcd(8, 12), gcd(36, 48)) 를 누적합 배열을 통해 나타낸다면, gcd(LR[1], RL[3]) 이 된다.

 

 

 

numbers 배열을 순회 할 때 index i를 제외한 최대공약수는 gcd(LR[i - 1], RL[i + 1])가 된다.

 

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

		static int N;
		static int[] numbers, LR, RL;
		
		public static void main(String[] args) throws IOException{
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			N = Integer.parseInt(br.readLine());
			
			numbers = new int[N];
			LR = new int[N];
			RL = new int[N];
			
            // N개의 수 입력받기
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}
			
            // 2개의 누적합 배열 채우기
			LR[0] = numbers[0];
			RL[N - 1] = numbers[N - 1];
			for (int i = 1; i < N; i++) {
				LR[i] = gcd(LR[i - 1], numbers[i]);
				RL[N - i - 1] = gcd(RL[N - i], numbers[N - i - 1]);
			}
			
            // N만큼 순회하면서 numbers[i]를 제외했을 때, 최대공약수가 제일 큰 값 찾기
			int k = 0;
			int maxGcd = 0;
			for (int i = 0; i < N; i++) {
				int leftP = i - 1;
				int rightP = i + 1;
				int getGcd = 0;
				if (leftP < 0) {
					getGcd = RL[rightP];
				}
				else if (rightP >= N) {
					getGcd = LR[leftP];
				} else {
					getGcd = gcd(LR[leftP], RL[rightP]);
				}
				if (getGcd > maxGcd) {
					maxGcd = getGcd;
					k = numbers[i];
				}
			}
			
            // 뺀 수를 K라고 했을 때, 나머지 수의 최대공약수가 K의 약수가 되면 안 된다.
			if (k % maxGcd == 0) {
				System.out.println(-1);
			} else {
				System.out.println(maxGcd + " " + k);
			}
			
			br.close();
			
		}
		
		// gcd(a, b) == gcd(b, r) : r = a % b
		static int gcd(int a, int b) {
			while (b != 0) {
				int r = a % b;
				a = b;
				b = r;
			}
			return a;
		}

	}

---

❗결과