[백준] 가로수 (2485번)

코드 힌트

1. 문제의 핵심:
   • 주어진 배열의 인접한 두 원소 간의 차이를 계산하여, 이들 차이의 최대 공약수(GCD)를 구합니다.
   • 이 GCD를 사용하여 배열의 원소들 사이의 가능한 모든 값을 체크하고, 누락된 값의 수를 계산합니다.
2. 차이 배열 계산:
   • 배열의 인접한 두 수의 차이를 계산하여 새로운 배열에 저장합니다.
   • 예를 들어, 배열이 arr이라면 인접한 두 원소의 차이를 계산하여 diffArr에 저장합니다.
3. 최대 공약수(GCD) 구하기:
   • 차이 배열의 모든 요소의 GCD를 구합니다.
   • GCD 계산에 필요한 두 매개변수를 사용하여 반복적으로 최대 공약수를 구합니다.
4. 결과 계산:
   • GCD를 사용하여 배열의 첫 번째 원소부터 시작해 GCD만큼 증가시켜 가며, 배열의 원소와 일치하는지 확인합니다.
   • 일치하지 않는 값의 수를 카운트하여 결과를 도출합니다.
5. GCD 계산 주의:
   • 최대 공약수를 계산할 때 배열의 모든 요소에 대해 반복적으로 GCD를 구합니다. 이 과정에서 나누기를 반복하여 나머지가 0이 될 때까지 진행합니다.

 

 

---

정답은 더보기 클릭

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int result = 0;
        int n = Integer.parseInt(in.nextLine());  // 입력받을 배열의 크기 n
        int[] arr = new int[n];  // 입력된 수를 저장할 배열
        int[] diffArr = new int[n-1];  // 인접한 수들 사이의 차이를 저장할 배열
        
        // 배열 arr에 수를 입력받아 저장
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(in.nextLine());
        }
        
        // 인접한 두 수의 차이를 계산하여 diffArr에 저장
        for (int i = 0; i < n-1; i++) {
            diffArr[i] = arr[i+1] - arr[i];
        }
        
        // 차이 배열의 최대 공약수(GCD)를 계산
        int gcd = gcd(diffArr);
        
        // 결과를 계산하기 위한 인덱스와 카운터
        int idx = 0;
        for (int i = arr[0]; i <= arr[n-1]; i+=gcd) {
            if (arr[idx] == i) {
                idx++;  // 현재 값이 배열의 원소와 일치하면 인덱스 증가
            } else {
                result++;  // 일치하지 않으면 추가된 값을 카운트
            }
        }
        
        // 결과 출력
        System.out.println(result);
    }
    
    // 배열의 최대 공약수를 구하는 메소드
    public static int gcd(int[] arr) {
        int result = arr[0];  // 초기 최대 공약수는 배열의 첫 번째 요소
        for (int i = 1; i < arr.length; i++) {
            // 배열의 모든 요소와 현재 최대 공약수의 GCD를 계산
            while (arr[i] > 0) {
                int tmp = result;
                result = arr[i];
                arr[i] = tmp % arr[i];
            }
        }
        
        return result;
    }
}