(JAVA) [BOJ]백준 17266번, 어두운 굴다리

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

17266번: 어두운 굴다리

17266, 어두운 굴다리

[ 난이도 : 실버 4 ]

이번 문제는 이분탐색을 사용해서 풀어보겠다.

 

# Process

input

: 굴다리의 길이 N, 가로등의 개수 M, 그리고 가로등의 위치 X가 주어진다.

 

static int N, M;
static int[] width;

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt();
    width = new int[M];
    for(int i=0; i<M; i++) width[i] = scan.nextInt();
}

 

이분탐색

: 굴다리의 길이 N을 비출 수 있는 가로등의 최소 높이를 출력해야 한다.

즉, 길이가 주어지고 순차적으로 위치가 주어졌을 때, 모든 굴다리를 비춰줘야 한다.

 

여기서 이분 탐색 이 가능한지 여부를 확인해야 한다.

가로등의 위치에서부터 주어진 길이로 직전 가로등이 비출 수 있는 범위에 겹칠 수 있다면 다음 가로등의 위치를 조회할 수 있다는 뜻이다.

 

예를 들어 처음 가로등의 위치는 2인 경우에 길이가 2로 주어졌다고 하자.

직전의 가로등이 없으니 0까지 모두 비출 수 있어야 한다.

그렇기 때문에 처음 prev 를 0으로 지정해주고 가로등의 위치 - 길이가 prev 보다 큰지 확인해준다.

그 후에 prev 를 witdh[i] (가로등의 위치) + target (길이) 로 스위칭해준다.

 

정리하면 매번 가로등 왼쪽의 위치를 모두 비추는지 확인하고 prev 를 가로등 + 길이로 바꿔주는 것이다.

모든 탐색을 마치고 나서 prev 가 N (가로등의 길이) 보다 큰지를 반환해준다.

static boolean possible(int target)
{
    int prev = 0;

    for(int i=0; i<M; i++)
    {
        if(width[i] - target > prev) return false;

        prev = width[i] + target;
    }

    return prev >= N;
}

static int binarySearch()
{
    int L = 1, R = N;

    while(L<=R)
    {
        int mid = (L+R)/2;

        if(possible(mid))
        {
            R = mid - 1;
        }
        else
        {
            L = mid+1;
        }
    }

    return L;
}

 

전체 코드

static int N, M;
static int[] width;

static void input() 
{
    N = scan.nextInt(); M = scan.nextInt();
    width = new int[M];
    for(int i=0; i<M; i++) width[i] = scan.nextInt();
}

static void pro() 
{   
    int ans = binarySearch();

    System.out.println(ans);
}

static boolean possible(int target)
{
    int prev = 0;

    for(int i=0; i<M; i++)
    {
        if(width[i] - target > prev) return false;

        prev = width[i] + target;
    }

    return prev >= N;
}

static int binarySearch()
{
    int L = 1, R = N;

    while(L<=R)
    {
        int mid = (L+R)/2;

        if(possible(mid))
        {
            R = mid - 1;
        }
        else
        {
            L = mid+1;
        }
    }

    return L;
}

public static void main(String[] args) 
{
    input();
    pro();	
}