[BOJ] 백준 17266. 어두운 굴다리

문제

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

---

풀이

세 가지 구역을 체크했습니다. 길 시작점부터 첫 가로등까지의 구역, 가로등과 가로등 사이의 구역, 그리고 마지막 가로등과 도착점의 구역입니다.

 

 세 가지 구역의 특징은 가로등과 가로등 사이면, 사이의 구간을 두 개의 가로등이 절반씩 나눠서 커버할 수 있다는 것이고 시작 구역과 도착 구역은 가로등 하나가 온전히 구간을 커버해야합니다. 

 

 그래서 아래처럼 세 구간으로 나누어 커버 범위의 최대 값을 구해주었습니다. 주의해야할 것은 만약 가로등과 가로등 사이 구간의 길이가 홀수라면, 사이의 길이/2 +1을 해주어야 한다는 것입니다. 홀수를 2로 나누기만 하면 중간을 커버하지 못하게 됩니다. (3이면 3/2 -> 1, 그러나 3을 1 두개로 커버하지 못함.)

 

 아래는 소스 코드입니다.

---

소스 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int firstDiff = sc.nextInt();
        int lastDiff = N;

        int maxDiff = 0;
        int tmp = firstDiff;
        for(int i = 1;i<M;i++){
            int x = sc.nextInt();
            maxDiff = Math.max(maxDiff,x-tmp);
            tmp = x;
            lastDiff = N-x;
        }
        int diff = 0;
        if(maxDiff%2==1) diff = maxDiff/2+1;
        else diff = maxDiff/2;
        
        int ans = Math.max(firstDiff,Math.max(lastDiff,diff));
        System.out.println(ans);
    }
}