[BOJ] 백준 1449 - 수리공 항승

1. 문제

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

1449번: 수리공 항승

 

2. 풀이

백준 실버 3 그리디 알고리즘 파트의 문제이다.
입력으로 주어지는 물이 새는 곳을 배열 OR 리스트에 넣고 정렬을 한다. (정렬하면 처음 위치점을 쉽게 찾을 수 있다.)
그 후 처음 물이 새는 곳을 찾고 그 곳에서 0.5를 뺀 값을 저장한다. 0.5를 빼는 이유는 좌우 0.5만큼 간격을 줘야 하기 때문이다. 한 곳을 테이프로 막았다면 그 곳에서 0.5를 뺀 곳이 테이프를 붙인 범위의 시작이 된다. 그리고 0.5를 뺀 값에서 테이프의 길이만큼 더해주면 테이프를 붙였을 때의 막은 범위가 된다.

예제를 통해 좀 더 자세히 알아보자.
예제 입력 1을 보면 물이 새는 곳은 4곳(1, 2, 100, 101), 테이프의 길이는 2이다.
정렬은 되어 있으므로 정렬을 따로 할 필요는 없고, 처음 물이 새는 지점은 1지점이다. 이 지점에 테이프를 붙이면 붙인 테이프가 막은 범위는 0.5 ~ 2.5가 된다. 이 범위안에 있는 물이 샌 곳은 테이프를 붙일 필요가 없는 것이다.

핵심을 짚었으니 이 핵심을 코드로 구현해보자.
우선 처음의 테이프의 개수를 1로 잡는다.(26줄)
1로 잡는 이유는 27줄에서 처음 물이 새는 지점을 테이프로 막고 범위를 구했으므로 1개를 이미 사용한 것이다.
그 후 반복문을 돌면서 이 범위에 테이프의 길이를 더한 지점보다 물이 새는 지점이 멀리 있다면 테이프 카운트를 하나 더해주고 범위를 다시 갱신해준다.

마지막으로 테이프의 개수(cnt)를 출력해주면 정답!!

3. 소스 코드

package greedy;

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());

        List<Integer> locationList = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            locationList.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(locationList);

        int cnt = 1;
        double range = locationList.get(0) - 0.5;
        for (int i = 0; i < locationList.size(); i++) {
            if (range + L < locationList.get(i)) {
                cnt++;
                range = locationList.get(i) - 0.5;
            }
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}