(Java) 백준 17266번

백준 17266번 실버4 정답률 39.557%

문제

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

입력

첫 번째 줄에 굴다리의 길이 N 이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 가로등의 개수 M 이 주어진다. (1 ≤ M ≤ N)

다음 줄에 M 개의 설치할 수 있는 가로등의 위치 x 가 주어진다. (0 ≤ x ≤ N)

가로등의 위치 x는 오름차순으로 입력받으며 가로등의 위치는 중복되지 않으며, 정수이다.

출력

굴다리의 길이 N을 모두 비추기 위한 가로등의 최소 높이를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int lastNum = Integer.parseInt(br.readLine());
		int startNum = 0;
		int totalCount = Integer.parseInt(br.readLine());
		double maxLength = 0;
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 0; i < totalCount; i++) {
			int target = Integer.parseInt(st.nextToken());
			double length = target - startNum;
			if(i == totalCount - 1) {
				double length2 = lastNum - target;
				if(length2 > maxLength) maxLength = length2;
			}
			if(i == 0) {
				if(length > maxLength) maxLength = length;
				startNum = target;
				continue;
			}
			length = Math.ceil(length / 2.0);
			if(length > maxLength) maxLength = length;
			startNum = target;
		}
		bw.write((int)maxLength + "");
        bw.flush();
        br.close();
        bw.close();
	}

}

나의 전략은 모든 가로등마다 좌측만 고려하고( 첫 번째 좌측은 온전히 혼자 비춰야하고 나머지는 좌측 비출 때 왼쪽 가로등이 오른쪽을 비추기 때문에 절반만 비추면 된다는 가정 ) 가장 우측 가로등만 우측을 고려하는 방식으로 로직 작성

(1) 첫 번째 가로등일 때 ( i == 0 ), 현재 가로등 위치 - 시작위치 거리까지 혼자 비춰야하기 때문에 maxLength 대상이고 startNum을 이용해서 현재 가로등 위치 저장

(2) 나머지 가로등일 때 ( i != 0 ), 현재 가로등 위치 - 이전 가로등 위치 거리까지 반만 비추면 되기 때문에 2로 나누고 소수점이 불가능해서 올림한 거리가 maxLength 대상이고 startNum을 이용해서 현재 가로등 위치 저장

(3) 마지막 가로등일 때 ( i == totalCount - 1 ), 마지막위치 - 현재 가로등 위치까지 혼자 비춰야하기 때문에 maxLength 대상

위 로직 상 maxLength 대상인 거리 중 가장 큰 값을 저장하고 출력하면 종료됩니다.

 

이상입니다. 지금까지 읽어주셔서 감사합니다.