[백준, Java] 14252번, 공약수열(정수론)

문제 링크

14252번: 공약수열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1. 서로 다른 양의 정수을 가진 크기 N의 집합  A가 주어집니다. 

2. 집합에 있는 수를 정렬했을 때 인접한 두 수의 최대 공약수가 1이 넘으면 안됩니다.

3. 추가해야 하는 수의 최대 개수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 정렬한 집합의 수를 추가해야 하는 경우를 탐색합니다.

 

3. 추가해야 하는 최소 횟수를 결과로 출력합니다.

 

 

수 추가하기

 

저는 집합을 정렬하는 기준을 오름차순으로 잡았습니다.

※ 최대 공약수를 GCD로 명칭하겠습니다.

 

수를 추가할 때에는 2가지 경우가 있습니다.

 

1. 이미 GCD가 1일 때

 

→ 이미 GCD가 1일 때에는 문제의 조건에 만족하기 때문에 수를 추가할 필요가 없습니다.

 

 

2. GCD가 1이 아닐 때(즉, 1이 아닌 공약수가 존재할 때)

 

→ 문제의 조건에 만족하기 위해서 수의 추가가 필요합니다.

 

 

수를 추가할 때에도 2가지 경우가 나뉩니다.

 

1. 인접한 두 수 사이에 값 중에서 모두 GCD가 1일 경우

 

→  해당 수만 추가하면 문제의 조건에 만족합니다.

 

1. 인접한 두 수 사이에 값 중에서 모두 GCD가 1인 경우가 없을 때

 

→  2개의 수를 추가해야 합니다.

 

2개의 수를 추가하는 이유.

 

두 수는 인접한 수와 1의 차이만 나는 수일 것입니다.

 

왜 1의 차이만 나는 수인가??

 

→ 두 수의 차이가 1이기 때문에 1을 제외한 수로 나머지를 구해도 1의 차이가 나기 때문에 나누어 떨어지지 않습니다.

 

→ 즉, GCD는 항상 1이 되기 때문입니다.

 

결과적으로 인접한 두 수와 1의 차이가 나는 수가 존재하기 때문에 2개를 추가하면 됩니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 4

 

2200

42

2184

17

 

2. 정렬한 집합의 수를 추가해야 하는 경우를 탐색합니다.

 

정렬하기

 

17

42

2184

2200

 

 

GCD(17, 42) : 1

 

→  수를 추가하지 않아도 됩니다.

 

 

GCD(42, 2184) : 42

 

→ 수를 추가해야 합니다.

 

두 수사이에 수에서 둘 다 GCD가 1이 되는 값에서 43이 존재합니다.

 

1개의 수 추가!

 

GCD(2184, 2200) : 8

 

→ 수를 추가해야 합니다.

 

두 수사이에 수에서 둘 다 GCD가 1이 되는 값이 존재하지 않습니다.

 

→ 2개의 수(2185, 2199)를 추가해야 합니다.

 

 

3. 추가해야 하는 최소 횟수를 결과로 출력합니다.

 

추가한 수 : 43, 2184, 2199

 

3을 결과로 출력합니다.

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 집합의 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort을 이용하여 집합을 오름차순 정렬하였습니다.
• 정렬된 집합의 인접한 값을 비교하며 수를 추가합니다.
• 추가한 수의 개수를 결과로 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• gcd함수는 유클리드 호재법을 이용하여 두 수의 GCD을 구합니다.

결과코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        //입력값 처리를 위한 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력을 위한 BufferedWriter
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] arr = new int[N];
        //입력된 N 크기의 집합 저장
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        //오름차순 정렬
        Arrays.sort(arr);
        int result = 0;
        //인접한 수 비교하여 수 추가하기
        for(int i=0;i<N-1;i++){
            //이미 두 수는 조건에 만족하기 때문에 넘기기
            if(gcd(arr[i], arr[i+1]) == 1){
                continue;
            }
            boolean flag = true;
            //두 수 사이의 값 중, GCD가 1인 값 찾아보기
            for(int j = arr[i]+1;j<arr[i+1];j++){
                //GCD가 1인 값이 존재할 때
                if(gcd(arr[i], j) == 1 && gcd(j, arr[i+1]) == 1){
                    flag = false;
                    break;
                }
            }
            //수 추가하기
            result++;
            //인접한 수들과 GCD가 1인 값이 존재하지 않을 때
            if(flag){
                result++;	// 두 수 추가하기
            }
        }
        //최소 추가횟수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //유클리드 호재법을 이용한 GCD 구하는 함수
    static int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b, a%b);
    }
}