[백준] 2485번 가로수 - JAVA

 

문제

 

https://www.acmicpc.net/problem/2485

2485번: 가로수

 

그럼 맨 처음 입력했던 수 (= 제일 가까운 가로수의 거리)와 맨 마지막에 입력했던 수 (= 제일 먼 가로수의 거리) 사이에 새롭게 심겠다는 의미가 되고 그 중에서 최소한으로 심겠다라는 의미입니다.

아래와 같이 그림과 함께 이해해보겠습니다.

 

 

 

 

그림이해 예시

 

1, 3, 7, 13을 입력했을 시

가로수 = 임의의 간격으로 이미 심어진 것

나무 = 일정 간격으로 최소한으로 심어야하는 것

예시1)

 

2, 5, 14, 20을 입력했을 시

가로수 = 임의의 간격으로 이미 심어진 것

나무 = 일정 간격으로 최소한으로 심어야하는 것

예시2)

 

입력

 

 

 

 

 

 

풀이

 

되게 시행착오를 많이 격고 생각보다 고민을 많이하게된 문제인 것같다.

처음에는 가로수 끼리 떨어진 거리들의 최대 공약수를 구하게 되었다.

바로 될 줄 알았지만 바로 문제를 틀리게 되었고 반례를 찾지 못하였지만 새로운 방법으로 접근하게 되었습니다.

똑같이 가로수 사이의 최대 공약수를 찾게 되었고 답을 도출할 때의 계산식을 다르게 하였습니다.

 

마지막에 계산식을 설명드리면 맨 처음 입력했던 수 (= 제일 가까운 가로수의 거리)와 맨 마지막에 입력했던 수 (= 제일 먼 가로수의 거리) 사이에 가로수와 나무가 존재하는 대신에 일정한 간격으로 있다는 말이므로

((맨 마지막 가로수 거리 - 맨 처음 가로수 거리) / 최대 공약수 ) - 이미 심어진 가로수의 수 + 1

위와 같은 식이 나오게 됩니다.

 

 

코드 설명은 주석으로 조금씩 달겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


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 distance = 0;

        List<Integer> list =new ArrayList<>();

        for(int i = 0; i < N; i++ ){
            list.add(Integer.parseInt(br.readLine()));		// 가로수 심기
        }
        Collections.sort(list);			// 정렬

        for(int i = 1; i < N; i++){
            int d = list.get(i) - list.get(i-1);		// 서로다른 가로수 거리 
            distance = gcd(d, distance);			// 최대 공약수 찾기
        }

        System.out.println( ((list.get(N-1) - list.get(0))/distance) -N+1  );

    }

	// 유클리드 호재법
    public static int gcd(int x, int y){
        if(y == 0){
            return x;
        } else {
            return gcd(y, x%y);
        }
    }
}

 

 

 

 

 

느낀점

 

코딩테스트에는 소수 문제가 잘 나오지는 않는다고 들었다.

그리고 소수 문제를 풀 때마다 내가 소수를 사용할 일이 생길까? 라는 의문이 들게 되고 수학을 되게 잘해야지만 풀 수 있는 문제가 많은거 같아서 답답했다.

익숙해 져야겠다.

 

 

 

 

 

 

감사합니다.