[백준_17266번] 어두운 굴다리

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

17266번: 어두운 굴다리

[문제]

 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히게 가로등을 설치해 달라고 인천광역시에 민원을 넣었다. 인천광역시에서 가로등을 설치할 개수 M과 각 가로등의 위치 x들의 결정을 끝냈다. 그리고 각 가로등은 높이만큼 주위를 비출 수 있다. 하지만 갑자기 예산이 부족해진 인천광역시는 가로등의 높이가 높을수록 가격이 비싸지기 때문에 최소한의 높이로 굴다리 모든 길 0~N을 밝히고자 한다. 최소한의 예산이 들 높이를 구하자. 단 가로등은 모두 높이가 같아야 하고, 정수이다.

 

다음 그림을 보자.

가로등의 높이가 H라면 왼쪽으로 H, 오른쪽으로 H만큼 주위를 비춘다.

 

다음 그림은 예제1에 대한 설명이다.

 

 

가로등의 높이가 1일 경우 0~1사이의 길이 어둡기 때문에 상빈이는 지나가지 못한다.

 

아래 그림처럼 높이가 2일 경우 0~5의 모든 길이 밝기 때문에 상빈이는 지나갈 수 있다.

 

 

[입력 조건]

• 첫 번째 줄에 굴다리의 길이 N 이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에 가로등의 개수 M 이 주어진다. (1 ≤ M ≤ N)
• 다음 줄에 M 개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 ≤ x ≤ N)
• 가로등의 위치 x는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

 

[코드]

import java.util.*;

public class BaekJoon_17266 {
	static int[] a;
	static int n,m;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		// 가로등이 설치된 지점 입력 받기
		a=new int[m];
		for(int i=0;i<m;i++)
			a[i]=sc.nextInt();
		
		int start=1;
		int end=n;
		int result=0;
		
		// 이진탐색
		while(start<=end) {
			int mid=(start+end)/2;
			
			// mid 높이로 모든 지점을 비출 수 있다면 result 갱신 후 높이를 줄여 재탐색
			if(possible(mid)) {
				result=mid;
				end=mid-1;
			}
			// 모든 지점을 비출 수 없다면 높이를 높여 재탐색
			else
				start=mid+1;
		}
		
		System.out.println(result);
	}
	
	static boolean possible(int target) {
		int prev=0; // 이전 가로등이 비춘 마지막 지점, 0 지점부터 모두 비춰주어야 하기 때문에 0부터 시작
		
		for(int i=0;i<a.length;i++) {
			/*
			 * 가로등이 있는 지점에서 비출 수 있는 높이(target)을 뺀 값이
			 * 이전 가로등이 비춘 마지막 지점에 도달했다면 prev 갱신
			 */
			if(a[i]-target<=prev) {
				prev=a[i]+target; // a[i] 가로등이 마지막으로 비춘 지점
			}
			/*
			 * 가로등의 시작 지점에서 높이(target)만큼 비춘 곳이
			 * 이전 가로등이 마지막으로 비춘 곳에 도달하지 못한다면 모든 지점을 비출수 없다. 
			 */
			else 
				return false;
		}
		
		/*
		 * 마지막 지점도 가로등이 비출 수 있는지 확인해야 하기 떄문에 
		 * 마지막 가로등이 비출 수 있는 끝 지점에서 굴다리의 끝 좌표를 뺐을 때
		 * 0보다 작거나 같아야 마지막 지점도 비춰지므로 해당 과정 필수!
		 */
		return n-prev<=0;
	}
}

 

[고찰] 

 이번 문제는 오랜만에 이진탐색 문제를 풀어보았다. 낮은 난이도의 문제를 선택했음에도 가로등이 모든 지점을 비출 수 있는지 확인하는 possible 함수를 작성하는데 어려움이 있었다. 

 가로등의 높이가 target일 때 모든 지점에 가로등의 불빛이 비춰지는지 확인하기 위해서는 이전 가로등이 마지막으로 비춘 지점을 저장하는 prev 변수가 필요하다. prev 변수는 0부터 모두 비춰야 하기 때문에 0으로 초기화 해놓고 가로등이 설치된 지점에서 가로등이 비출 수 있는 거리인 target을 뺀 값이 prev보다 같거나 작아야한다. 여기서 제일 중요한 점은 굴다리의 마지막 지점도 비춰지는지 확인해야 한다는 것이다. 이 과정을 빠뜨려 오답 처리를 받았는데 이유를 한참 고민했다. 굴다리의 마지막 지점인 n에서 마지막 가로등이 비추는 prev를 뺀 값이 0보다 작거나 같아야 가로등이 target 높이로 마지막 지점까지 모든 굴다리를 비추는 경우가 된다.