[Java] 백준알고리즘 #2485 가로수

백준알고리즘 #2485 가로수

 

가로수를 같은 간격으로 심기 위한 최소수를 구하는 문제.

각 가로수 간격들의 최대공약수를 구하는 것으로 해결할 수 있어 보인다.

예제 1에서

간격들이 2 4 6이기 때문에 이들의 최대공약수는 2이고

1부터 13까지의 거리는 12이고, 이를 최대공약수로 나누면 6이 된다.

즉 1부터 13까지의 좌표 상에 총 7개 (시작점과 끝점)의 가로수가 있다고 볼 수 있다.

입력(가로수의 개수)는 4이므로 심어야하는 가로수의 최소수는 3이 되는 것이다.

 

조건에서 n은 3이상이고, 두 좌표 사이의 거리가 필요하기 때문에 처음 두 가로수의 좌표를 먼저 입력받는다.

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int first = sc.nextInt(); // 첫번째 가로수 위치
int after = sc.nextInt(); // 두번째 가로수 위치

int gcd = after - first; // 거리의 최대공약수

당연히 아직까지 거리들의 최대 공약수는 두 가로수 사이의 거리가 된다.

 

이제 3번째 가로수부터 반복문을 통해 입력받고, 2번째 가로수와의 거리를 계산하여 앞서 구해두었던 최대공약수(gcd)와의 최대공약수를 구한다.

이 때, 유클리드 호제법을 이용하면 간단하다.

2023.10.10 - [Java/백준알고리즘] - [Java] 백준알고리즘 #13241 최소공배수

[Java] 백준알고리즘 #13241 최소공배수

 

for (int i = 2; i < n; i++) {
    int tree = sc.nextInt(); // 가로수 위치
    int dis = tree - after; // 두 나무 사이의 거리 

    if (gcd > dis) { // dis가 더 크도록 치환
        int tmp = gcd;
        gcd = dis;
        dis = tmp;
    }
    while (true) {// 유클리드 호제법으로 이전까지 구했던 최대공약수와 최근 두 나무사이의 거리의 최대공약수를 구함
        int tmp = dis % gcd;
        if (tmp == 0) {
            break;
        }
        dis = gcd;
        gcd = tmp;
    }
    after = tree;
}

 

이제 전체 거리를 구하고, 이를 최대공약수로 나눈 후, 심어져있는 나무 수를 빼면 된다.

int all = after - first; // 전체 거리
System.out.println(all / gcd - n + 1); // 전체거리 / 최대공약수 - 심어져 있는 나무 수 + 1 (시작점)

 

전체 코드는 다음과 같다.

 

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int first = sc.nextInt(); // 첫번째 가로수 위치
        int after = sc.nextInt(); // 두번째 가로수 위치

        int gcd = after - first; // 거리의 최대공약수
        for (int i = 2; i < n; i++) {
            int tree = sc.nextInt(); // 가로수 위치
            int dis = tree - after; // 두 나무 사이의 거리 2

            if (gcd > dis) { // dis가 더 크도록 치환
                int tmp = gcd;
                gcd = dis;
                dis = tmp;
            }
            while (true) {// 유클리드 호제법으로 이전까지 구했던 최대공약수와 최근 두 나무사이의 거리의 최대공약수를 구함
                int tmp = dis % gcd;
                if (tmp == 0) {
                    break;
                }
                dis = gcd;
                gcd = tmp;
            }
            after = tree;
        }
        int all = after - first; // 전체 거리
        System.out.println(all / gcd - n + 1); // 전체거리 / 최대공약수 - 심어져 있는 나무 수 + 1 (시작점)

        sc.close();
    }
}

 

얼핏 복잡해 보일 수 있지만, 심어야 하는 가로수의 수를 구하기 위해 거리들의 최대공약수를 구해야 한다는 점을 파악하면 쉽게 해결할 수 있는 문제인 듯 하다.