백준 BaekJoon 2485번: 가로수 [Java] 자바

2020-10-18

---

문제

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

KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

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

 

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

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

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3≤N≤100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 100,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

출력

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

---

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int tree = Integer.parseInt(bf.readLine());
		
		int [] arr = new int [tree];
		int [] temp = new int [tree];
		
		int max = 10000000;
		//각 배열의 차이값중 최솟값이 되는것이
		//등차에서 가질수있는데 max 값이다.
		for(int i = 0; i < tree; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
			temp[i] = arr[i];
		}
		
		for(int i = 0; i < tree - 1; i++) {
			if(arr[i + 1] - arr[i] < max) {
				max = arr[i + 1] - arr[i];
			}
		}
		
		int count = 0;
		//가로수 갯수 셀변수
		int minCount= 10000000;
		
		int plus = 1;
		if(max != 1) {
			plus = max / 2;
				}
		//등차변수
		int i = 0;
		//배열 위치 지정변수
		while(true) {
			
			if(max < plus) {
				break;
			}
		
			
			do{	
			if(temp[i] + plus == temp[i + 1]) {
				i++;
				//플러스값을 더할때 다음값과 같으면
				//카운트 필요없이 위치만 이동
				}else if(temp[i] + plus < temp[i +1]) {
					count++;
					temp[i] = temp[i] + plus;
					//풀러스 한 값이 작으면,
					//위치 바꿀필요 없이 현재 위치에서 플러스만
					//더해주고 카운트 더해줌
				}else {
					count = 99999;
					//등차를 이루지 않기 때문에 멈추고
					//카운트에 큰값을 넣어주어
					//mincount에 들어가지 않게함
					break;
				}
			}while(i < tree-1);
			//i의 값이 마지막 위치가 되면 종료함
			
			if(count < minCount) {
				minCount = count;
			}
			
			count = 0;
			i = 0;
			plus++;
			//사용변수 초기화
			//플러스는 다음 등차비교 위해 하나 더해줌
		
			for(int reset = 0; reset < tree; reset++) {
				temp[reset] = arr[reset];
			}
			//temp 배열 초기화 시켜줌
			
		}
		
		System.out.println(minCount);
	}

 

출처 링크 : www.acmicpc.net/problem/2485

2485번: 가로수