[백준][Java] 2485번 가로수

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 2485 가로수

오늘 문제는 이미 심어져 있는 가로수 사이에 새로 나무를 심어 모든 가로수가 같은 간격이 되도록 하려면,

최소 몇 그루의 나무를 더 심어야 하는지를 구하는 문제입니다.

 

📘 문제

 

💡 해결 방법

모든 나무가 동일한 강격을 가지도록 하기 위해 모둔 간격의 최대공약수(GCD)를 기준 간격으로 사용해야 합니다.

그리고 간격마다 중간에 몇 그루를 더 심어야 하는지 계산하면 됩니다.

GCD에 대한 더 자세한 내용이 필요하시다면 아래 링크에서 확인 바랍니다.

[백준][Java] 1934번 최소공배수

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

 

• 먼저 나무 사이의 간격 차이(diff) 를 모두 구합니다.
• 그 모든 간격들의 최대공약수(GCD) 를 구합니다.
• 각 간격마다 (간격 / GCD - 1)개의 나무가 필요합니다.
• 모든 간격에 대해 필요한 나무 수를 더해주면 정답입니다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        // 심어져 있는 가로수
        int[] trees = new int[n];
        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(br.readLine());
        }
        
        // 각 가로수 사이 간격 구하기 (뒷나무 - 앞나무)
        int[] diffs = new int[n - 1];
        for (int i = 1; i < n; i++) {
            diffs[i - 1] = trees[i] - trees[i - 1];
        }
        
        // 최대공약수 구하기 (나무 간격에 몇개의 나무가 심어져야 하는지)
        int gcd = diffs[0];
        for (int i = 1; i < diffs.length; i++) {
            gcd = getGCD(gcd, diffs[i]);
        }
        
        // 새로 심어야 하는 나무 수 (간격 / 최대공약수 - 1 (-1은 이미 심어져 있는 나무))
        int result = 0;
        for (int diff : diffs) {
            result += diff / gcd - 1;
        }
        
        System.out.print(result);
        br.close();
    }
    
    private static int getGCD(int a, int b) {
        if (b == 0 ) return a;
        return getGCD(b, a % b);
    }
}

 

이 문제는 단순 구현 문제가 아니라 수학적 사고가 중요한 문제였어요.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)