[이진탐색 모음] BOJ #2110 공유기 설치, #10816 숫자카드, #2343 기타레슨

#2110 공유기 설치

문제 이해

처음에는 문제 이해가 가지 않았다.... 흠냐

문제를 이해하자면 우선, '거리'에 집중하면 된다.

 

1. 집 n 개가 있다.

2. 집의 좌표가 주어진다.

3. 공유기의 개수가 주어진다.

4. c개의 공유기를 n개의 집에 설치한다.

5. 이때 최대 거리를 출력한다.

 

 

 

 

해결방법 고안

'이진탐색'으로 접근하자

 

나는 이진탐색 문제라고 해서 항상 하던 것처럼 인덱스를 잘라서 접근하려고 했다..

근데 이번에는 거리에 이진탐색으로 반씩 줄여서 접근하면 된다.

최소부터 최대까지, 공유기를 설치할 수 있는 수에서 거리의 최댓값을 구하면 되는 것이다

 

나는 무슨 단어에 집착하는 경향이 있는데 이번에도 '인접한'이라는 단어에 넘어가서 좀 헤맸다. ㅜ_ㅜ

이진탐색으로 구한 거리를 사용해서 집에 설치, 그 집 좌표에 + 거리 해준다음 다음 집에 또 설치하는 식이다.

 

 

코드 설명

 

입력을 다 받은 후, 시작 점과 도착점을 고정해둔다.

거리의 최소값은 1이고 최대값은 home 배열의 마지막 값이다.

int start = 1;
int end = home[n-1];

 

 

확인하는 집이랑 전집이랑 차이가 mid보다 크다면 그 확인하는 집에 공유기를 설치한다.

공유기의 개수는 cnt로 두고 전집은 preHome으로 저장해두었다.

int cnt =1;
int preHome = home[0];

for(int i=1; i<n; i++){
	if(home[i] - preHome >= mid){ //설치
    	cnt++;
    	preHome = home[i];
    }
}

 

 

이렇게 공유기를 설치했는데 cnt랑 c랑 동일하면 혹시 모를 최대 거리가 있을 수 있으니까 거리를 늘려준다.

그리고 공유기의 개수가 모자란 경우에는 거리를 늘려준다.

if(c <= cnt){ //공유기 설치 완료 했는데 더 놓을 수 있는 경우, 최소 거리를 늘릴 수 있음
    res = mid;
    start = mid + 1;
}
else{
    end = mid - 1;
}

 

설치된 공유기의 개수가 더 적으면 거리가 너무 늘렸다는 거니가 좁혀주기 위해서 end = mid-1를 하는 것이다.

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Boj2110 {
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static int n,c;
	static int []home;
	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(input.readLine());
		n = Integer.parseInt(tokens.nextToken());
		c = Integer.parseInt(tokens.nextToken());
		home = new int[n];
		for(int i=0; i<n; i++) {
			home[i] = Integer.parseInt(input.readLine());
		}
		Arrays.sort(home);
		int start = 1;
		int end = home[n-1];
		int res=0;
		while(start <= end){
			int mid = (start + end ) /2; //거리
			int cnt =1;
			int preHome = home[0];

			for(int i=1; i<n; i++){
				if(home[i] - preHome >= mid){
					//설치
					cnt++;
					preHome = home[i];
				}
			}
			if(c <= cnt){ //공유기 설치 완료 했는데 더 놓을 수 있는 경우, 최소 거리를 늘릴 수 있음
				res = mid;
				start = mid + 1;
			}
			else{
				end = mid - 1;
			}
		}
		System.out.print(res);
	}
}

 

 

#10816 숫자카드 2

문제이해

m배열에서 숫자에 해당하는게 n에 몇개 있는지 구한다.

 

해결방법고안

개수를 파악하기 위해서

이진탐색으로 인덱스 중에 제일 작은걸 구하고, 인덱스 중에 제일 큰걸 고른다.

그 다음에 큰거 - 작은거 +1 를 하게 되면 총 개수가 나오게 된다.

 

전체코드

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

public class Main {
	static StringTokenizer tokens;
	static StringBuilder output = new StringBuilder();
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static int n,m;
	static int []nArr, mArr;
	public static void main(String[] args) throws IOException {
		n = Integer.parseInt(input.readLine());
		nArr = new int[n];
		tokens = new StringTokenizer(input.readLine());
		for(int i = 0; i < n; i++){
			nArr[i] = Integer.parseInt(tokens.nextToken());
		}
		m = Integer.parseInt(input.readLine());
		mArr = new int[m];
		tokens = new StringTokenizer(input.readLine());
		for(int i = 0; i < m; i++){
			mArr[i] = Integer.parseInt(tokens.nextToken());
		}
		Arrays.sort(nArr);
		getIdx();
		System.out.print(output);
	}
	private static void getIdx(){
		int mid = n/2;
		for(int i : mArr){
			int l = left(i);
			int r = right(i);
			if(l ==-1 & r ==-1){
				output.append(0+" ");
			}
			else{
				output.append(r - l +1 + " ");
			}
		}
	}
	//m차례대로 x이 인덱스
	static int left(int x){
		int start = 0;
		int end = n-1;
		int idx=-1;
		while(start <= end) {
			int mid = (start + end ) /2;
			if(nArr[mid] == x){
				idx = mid;
				end = mid-1;
			}
			else if(nArr[mid] > x){
				end = mid-1;
			}
			else {
				start = mid+1;
			}
		}
		return idx;
	}
	static int right(int x){
		int start = 0;
		int end = n-1;
		int idx=-1;
		while(start <= end) {
			int mid = (start + end ) /2;
			if(nArr[mid] == x){
				idx = mid;
				start = mid + 1;
			}
			else if(nArr[mid] > x){
				end = mid-1;
			}
			else {
				start = mid+1;
			}
		}
		return idx;
	}
}

 

 

#2343 기타 레슨

문제이해

블루레이 총 N개가 있다. 순서대로 m개만큼 묶음으로 넣어야한다. 그 각 넣은 합의 최소를 구해야 한다.

예를 들어, 123456가 순서대로 주어져있으면 1234, 56 이렇게 넣어야 하고 11은 블루레이의 최소 크기가 될 것이다.

이것처럼 순서를 바꾸지 않고 블루레이에 답을 수 있는 합의 최소를 구하면 되는 것이다.

 

 

해결방법 고안

'이진탐색'으로 크키를 구하면 된다. 이진탐색 문제를 좀 풀어보니 구하고자 하는 것에 초점을 맞춰서 그것으로 이진탐색을 하면 되었다.

그래서 이 문제는 합의 크기를 이진탐색으로 두면 된다. 최소의 값은 블루레이 중 가장 큰 값으로, 최대의 값은 블루레이 총 합으로 두자

그 합을 조정해나가면서 블루레이의 개수를 구하고 블루레이의 개수가 > m 이라면 크키를 늘리는 start = mid +1하고 블루레이 개수 < m이라면 end = mid-1을 하면 됩니더

 

 

전체 코드

package boj;
import java.io.*;
import java.util.*;

public class Boj2343 {
    static StringTokenizer tokens;
    static StringBuilder output = new StringBuilder();
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static int n, m;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        n = Integer.parseInt(tokens.nextToken());
        m = Integer.parseInt(tokens.nextToken());
        arr = new int[n];

        tokens = new StringTokenizer(input.readLine());
        int end = 0; // 전체 합은 블루레이의 최대 크기
        int maxVal = 0; // 가장 큰 값은 블루레이 크기의 최소 시작점

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(tokens.nextToken());
            end += arr[i];
            maxVal = Math.max(maxVal, arr[i]); // 최대값을 저장 (start의 초기값)
        }

        // 이진 탐색의 시작점은 가장 큰 강의의 길이, 끝점은 전체 강의 길이 합
        int start = maxVal;
        int res = 0;

        while (start <= end) {
            int mid = (start + end) / 2;
            int sum = 0;
            int cnt = 1; // 블루레이 개수 (최소한 한 개는 필요)

            for (int i = 0; i < n; i++) {
                if (sum + arr[i] > mid) { // 현재 블루레이에 못 담으면 새 블루레이 사용
                    cnt++;
                    sum = arr[i];
                } else {
                    sum += arr[i];
                }
            }

            if (cnt <= m) { // 블루레이 수가 m 이하이면 더 작은 크기를 시도
                res = mid;
                end = mid - 1;
            } else { // 블루레이 수가 m보다 많으면 크기를 늘려야 함
                start = mid + 1;
            }
        }

        System.out.println(res);
    }
}