[백준 1449번] 수리공 항승 (Java 풀이)

백준알고리즘 1449번 : 수리공 항승

 

 

필요한 테이프의 갯수를 출력하는 문제이다.
어차피 구멍을 왼쪽부터 정렬하게되면, 무조건 왼쪽부터 커버해야하기 때문에 문제가 한결 쉬워질 것이라고 판단했다.

 

 

풀이 과정

---

1. 구멍의 위치를 오름차순으로 정렬한다.
2. 남아있는 테이프의 위치(왼쪽 끝, 오른쪽 끝)를 확인하고,
    앞, 뒤를 다 커버가능한지 매번 체크하도록 한다
3. 커버가 불가능하다면 테이프 갯수를 하나 더 늘이고, 테이프가 커버할수 있는 위치를 초기화한다.

 

 

소스 ▽

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {// No1449 : 수리공 항승

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine());

        int holes = Integer.parseInt(st1.nextToken());
        int tape = Integer.parseInt(st1.nextToken());

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] hole = new int[holes];

        for (int i = 0; i < holes; i++) {
            hole[i] = Integer.parseInt(st2.nextToken());
        }

        Arrays.sort(hole);

        int ans = 0;
        double leftLen = 0;
        double rightLen = 0;

        for (int i = 0; i < holes; i++) {
            if (leftLen <= (double) hole[i] - 0.5 && (double) hole[i] + 0.5 <= rightLen) {
                continue;
            } else {
                ans++;
                leftLen = hole[i] - 0.5;
                rightLen = hole[i] - 0.5 + tape;
            }
        }

        System.out.println(ans);

    }
}