백준 1449 - 수리공 항승 (자바 - 그리디)

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

1449번: 수리공 항승

 

* 문제 요약

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L 인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때 적어도 그 위치의 0.5 만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L 이 주어졌을 때, 항승이가 필요한 테이프의 최소 갯수를 구하는 프로그램을 작성하시오.

테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

 

* 입력

첫째 줄에 물이 새는 곳의 갯수 N 과 테이프의 길이 L 이 주어진다.

둘째 줄에는 물이 새는 곳의 위치가 주어진다.

N 과 L 은 1,000 보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000 보다 작거나 같은 자연수이다.

 

* 출력

첫째 줄에 항승이가 필요한 테이프의 갯수를 출력한다.

 

* 예시

 

* 해결 과정

구멍이 난 곳들이 가장 왼쪽에서부터 정수만큼 떨어진 곳에 위치해 있는 반면에 입력은 반드시 오름차순으로 들어온다는 보장이 없으므로, 구멍이 난 곳의 위치를 입력받은 다음 이를 오름차순으로 정렬해준다.

 

그 다음 테이프를 처음 붙이는 시작점의 위치를 구멍이 난 곳들 중 가장 왼쪽에 있는 곳에서 0.5 만큼 떨어진 곳으로 저장해준 다음 테이프의 갯수를 1로 늘려주고 입력받은 구멍의 위치가 저장된 배열의 처음부터 끝까지 범위동안 아래와 같이 반복문을 수행한다.

- 시작점 위치 + 테이프의 길이 보다 구멍의 위치가 더 멀리 있는 경우 테이프의 갯수를 1 늘리고 시작점의 위치를 해당 구멍의 위치 - 0.5 지점으로 초기화해준다.

- 시작점의 위치 + 테이프의 길이 보다 구멍의 위치가 더 작다면 기존에 시작점에서 붙였던 테이프 하나의 길이만으로 충분히 해당 위치의 구멍을 메울 수 있다는 뜻이므로 아무런 로직도 수행하지 않는다.

(테이프를 사용하는 갯수를 최소화 하기 위한 로직)

- 여기서 시작점의 위치 + 테이프의 길이를 계산하면 n + 0.5 와 같은 식으로 결과가 나오는데 이는 구멍을 메울 때 위의 길이보다 작은 위치에 구멍이 존재하는 경우 구멍의 오른쪽 부분까지 0.5 만큼 늘려서 붙여주는 의미로도 해석할 수 있다.

 

* 코드

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

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));

        String[] inputArray = br.readLine().split(" ");
        int water = Integer.parseInt(inputArray[0]);
        int tapeLength = Integer.parseInt(inputArray[1]);

        inputArray = br.readLine().split(" ");
        Integer[] waterArray = new Integer [water];
        for(int i = 0; i < waterArray.length; i++){
            waterArray[i] = Integer.parseInt(inputArray[i]);
        }

        Arrays.sort(waterArray);

        int tapeCount = 0;
        double start = waterArray[0] - 0.5;
        tapeCount = 1;
        for(int i = 0; i < waterArray.length; i++){
            // 시작 지점 + 테이프의 길이 값 보다 현재 구멍의 위치가 더 길 경우 테이프 갯수 추가 및 start 변수 초기화
            if(start + tapeLength < waterArray[i]){
                tapeCount++;
                start = waterArray[i] - 0.5;
            }
        }
        
        bw.write(tapeCount + "\n");
        bw.flush();
        bw.close();
        br.close(); 
    }
}

 

사용되는 테이프의 갯수를 최소화 하기 위해 매 반복마다 조건에 맞을 경우 시작점을 초기화 해가며 시작점 + 테이프의 길이 내부에 포함되는 구멍들을 한번에 메워지게 만들었다.

시작점 + 테이프의 길이 보다 먼 거리에 있는 구멍에 대한 처리, 그보다 더 작은 거리에 있는 구멍에 대한 처리를 매 반복마다 초기화 되는 시작점의 위치에 맞춰, 즉 매 단계마다 현재 상황에 맞춰 최적의 로직을 수행하도록 만들었으므로 그리디 알고리즘 문제라고 할 수 있다.