[백준] 2485 - 가로수 (JAVA)

1. 소요시간 : 23분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 4
4. 문제 유형 : 수학, 정수론, 유클리드 호제법
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/2485
8. 푼 날짜 : 2023.03.20

1. 사용한 자료구조 & 알고리즘

최대 공약수를 구하는 유클리드 호제법을 사용했다.

2. 사고과정

개인적으로 실버 4보다는 난이도가 더 높았다고 생각한다.
실버 1~2정도의 난이도라고 느꼈다.
처음에는 그리디 알고리즘일 거라고 생각했다.
하지만 이내 최대공약수를 구해야 한다는 사실을 알게 되었다.

가장 많이 고민한 것은 모든 수들의 최대 공약수를 구한 후 그다음에 어떻게 설치하느냐이다.
예제입력 1의 경우에는 최대 공약수 2를 구했는데 이제 그다음에 1부터 2씩 더해주며 1,3,5,7,9,11,13 을 체크하며 현재 숫자가 arr배열에 없는 경우에는 count를 증가시켜주려고 했다.
하지만 가로수를 나타내는 정수가 1,000,000,000 이고 최대공약수가 1이라면 1씩 더해주며 1억을 1초로 본다면 10초가 나온다.

그래서 어떻게 해주면 될까 고민을 하다가 좌표까지는 알 필요가 없으니, 최대값과 최소값의 차이, 그리고 배열의 길이를 안다면 원하는 값을 도출해낼 수 있다는 결론에 도달했다.

3. 풀이과정

1. 자료들이 크기 순으로 주어진다는 말은 없으니 자료를 정렬한다.
2. 각각 자료들마다의 값의 차이를 저장한다.
3. 자료의 값의 차이들의 최대공약수를 구한다.
4. 설치해야 하는 가로수의 개수는
   ( (가장 큰 좌표 - 가장 작은 좌표)/최대 공약수 ) - N + 1 이다.

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int arr[]=new int[N];
		for(int i=0;i<arr.length;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		int gap[]=new int[arr.length-1];
		
		for(int i=0;i<gap.length;i++) {
			gap[i]=arr[i+1]-arr[i];
		}
		for(int i=1;i<gap.length;i++) {
			gap[i]=gcd(gap[i],gap[i-1]);
		}
		
		int num=gap[gap.length-1];
		
		int value=(arr[arr.length-1]-arr[0])/num-arr.length+1;
		
		System.out.println(value);
		
		
	}
	public static int gcd(int a,int b) {
	
		while(b!=0) {
			int r=a%b;
			a=b;
			b=r;
		}
		return a;
	}
}

5. 결과

6. 회고

생각보다 어려웠다.
가로수의 위치가 1,000,000,000 까지니
TLE 를 어떻게 피할 수 있을까 고민을 많이 했다.

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212