[BOJ][JAVA] 2110번: 공유기 설치

 

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

2110번: 공유기 설치

 

 

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

public class Main {
	static int[] home;
	static int n;
	static int c;

	static int parametric() {
		int l = 0;
		int r = n - 1;
		int m = 0;
		while (l < r) {
			m = (l + r) / 2;
			if ((home[m] - home[l]) * (c - 2) <= home[r] - home[m]) { // yes
				l = m + 1;
			} else {
				r = m - 1;
			}
		}

		return home[m - 1] - home[0];
	}

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		home = new int[n];
		// 그래프 초기화
		for (int i = 0; i < n; i++) {
			home[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(home);
		//System.out.println(Arrays.toString(home));

		System.out.println(parametric());
	}
}

---

오답노트(푸는 동안 사고과정 및 개선점)

파라메트릭 서치라는 개념을 처음 알게 됐다.

파라메트릭 서치를 간결하게 정리하면 결정 조건이 추가된 이분탐색이다. 이분탐색이 큰 범위, 작은 범위를 좁혀가며 logN으로 탐색하는 알고리즘인데 이때 범위를 좁힐 조건을 추가한 게 파라메트릭 서치라는 개념이다.

 

이분 탐색을 다시 생각해보자. m = (l + r) /2 으로, m이 커서일 때
m이 타겟보다 작으면 -> l을 m+1로 땡겨오고

m이 타겟보다 크면 -> r을 m-1로 땡겨온다

이때 m과 타겟을 비교하는 부분을 떼다가 내가 찾아야되는 조건으로 바꾸면 완성이다.

 

오답이후 내가 만든 조건은 아래와 같다.

static int count(int m) { // 공유기 개수 세기
		int cnt = 1; // 시작점에 설치하고 시작함.
		int prev = home[0];

		for (int i = 1; i < n; i++) {
			int d = home[i] - prev; // 현재 지점부터 i번째 집까지의 거리를 계산하기
			if (d >= m) { // m보다 현재 거리가 크거나 같으면 공유기를 놓고 거리 갱신
				cnt++;
				prev = home[i]; // 이러면 다음 갱신될 거리는 늘어나게 됨 -> c만큼 공유기 설치하면 최장거리 완성
			}
		}
		return cnt;
}

cnt가 설치할 수 있는 공유기 개수다. 공유기를 C개 만큼 설치할 수 있으면 그게 종료 조건이 될 수 있는데 그건 이 count 함수를 돌면서 결정한다.

파라미터로 m이 들어오면 이때 m은 공유기를 설치하기위해 이동할 시작 거리다.

---

정답코드

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

public class Main {
	static int[] home;
	static int n;
	static int c;

	static int count(int m) { // 공유기 개수 세기
		int cnt = 1; // 시작점에 설치하고 시작함.
		int prev = home[0];

		for (int i = 1; i < n; i++) {
			int d = home[i] - prev; // 현재 지점부터 i번째 집까지의 거리를 계산하기
			if (d >= m) { // m보다 현재 거리가 크거나 같으면 공유기를 놓고 거리 갱신
				cnt++;
				prev = home[i]; // 이러면 다음 갱신될 거리는 늘어나게 됨 -> c만큼 공유기 설치하면 최장거리 완성
			}
		}
		return cnt;
	}

	static int parametric() {
		int l = 0;
		int r = home[n - 1] - home[0];// 최대 거리 -> 사람 위치 수가 아니라 거리를 기준으로 잡는다.
		
		int ans = 0;

		while (l <= r) {
			int m = (l + r) / 2;
			int cnt = count(m);
			if (cnt >= c) { // 공유기 늘릴 수 있음
				ans = m;
				l = m + 1;
			} else { // 공유기 줄여야 함
				r = m - 1;
			}
		}

		return ans;
	}

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());

		home = new int[n];
		// 그래프 초기화
		for (int i = 0; i < n; i++) {
			home[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(home);
		//System.out.println(Arrays.toString(home));

		System.out.println(parametric());
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^