백준 2485 가로수 [JAVA]

리뷰

시간초과

• 모든 수를 각각 비교해 최대공약수(간격)를 계산한 뒤, 모든 가로수 값을 HashSet에 저장해 중복을 확인했다.

 

시간초과 문제를 해결하기 위해 유클리드 호제법으로 최대공약수를 구하고, 추가한 가로수는 HashSet에 저장하지 않고 count++ 연산으로 체크했다.

 

두 부분 다 수정해야 한다.

HashSet을 삭제해도 모든 수를 반복문 돌려서 최대공약수를 구하면 시간초과가 뜨고, 유클리드호제법을 사용해 최대공약수를 구하더라도 HashSet으로 개수를 카운트하면 메모리 초과가 뜬다.

 

공부한 것

• 여러수의 최대공약수 - 유클리드호제법

먼저 두 수를 골라 최대공약수를 구한다.
그 값(최대공약수)과 남은 수 중 하나의 최대공약수를 구한다. 
위 과정을 반복한다.

• 두수의 최대공약수 - 유클리드호제법

//큰수 max, 작은수 min

int temp = 0;
while (min != 0) {
		temp = max % min;
		max = min;
		min = temp;
	}
	result = max;
   }

 

문제

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

예제 입력 1 복사

4
1
3
7
13

예제 출력 1 복사

3

예제 입력 2 복사

4
2
6
12
18

예제 출력 2 복사

5

 

내 답안

1. 모든 수를 각각 비교해 최대공약수(간격)를 구한 뒤, 모든 가로수 값을 HashSet에 저장해 중복 확인 (시간초과)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		HashSet<Integer> hs = new HashSet<>();
		ArrayList<Integer> list = new ArrayList<>();
		ArrayList<Integer> listMinus = new ArrayList<>();
		ArrayList<Integer> listGCD = new ArrayList<>();
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int k = Integer.parseInt(br.readLine());
			list.add(k);
			hs.add(k);
		}
		for (int i = 1; i < n; i++) {
			listMinus.add(list.get(i) - list.get(i-1));
		}
		for (int i = 0; i < listMinus.size(); i++) {
			int gcd = 0;
			for (int j = i + 1; j < listMinus.size(); j++) {
				int min = Math.min(listMinus.get(i), listMinus.get(j));
				for (int h = 1; h < min; h++) {
					if (listMinus.get(i) % h == 0 && listMinus.get(j) % h == 0) {
						gcd = j;
					}
				}
			}
			if (gcd > 0) {
				listGCD.add(gcd);
			}
		}
		Collections.sort(listGCD);
		int interval = listGCD.get(0);
		int k = list.get(0);
		int count = 0;
		while (k < list.get(list.size() - 1)) {
			k += interval;
			if (k < list.get(list.size() - 1)) {
				if (hs.add(k)) {
					count++;
				}
			}
		}
		bw.write(count + "\n");
		bw.flush();
	}
}

 

2. 유클리드 호제법, HashSet대신 count++ 사용

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		ArrayList<Integer> list = new ArrayList<>();
		ArrayList<Integer> listInterval = new ArrayList<>();
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int k = Integer.parseInt(br.readLine());
			list.add(k);
		}
		for (int i = 1; i < n; i++) {
			listInterval.add(list.get(i) - list.get(i - 1));
		}
		int min = listInterval.get(0);
		for (int i = 1; i < listInterval.size(); i++) {
			int x = 0;
			int max = listInterval.get(i);
			while (min != 0) {
				x = max % min;
				max = min;
				min = x;
			}
			min = max;
		}
		int interval = min;
		int k = list.get(0);
		int count = 1;
		while (k < list.get(list.size() - 1)) {
			k += interval;
			if (k <= list.get(list.size() - 1)) {
				count++;
			}
		}
		int result = count - list.size();
		bw.write(result + "\n");
		bw.flush();
	}
}