[백준, Java] 1911번, 흙길 보수하기(그리디)

문제 링크

1911번: 흙길 보수하기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

1.  널빤지는 L의 길이를 가지고 있으며 물웅덩이에 다리를 만들 수 있습니다.

2. 모든 웅덩이의 다리를 만들어 덮는 최소의 널빤지 수를 결과로 출력합니다.

3. 구덩이의 범위는 S ≤ 웅덩이 ＜ E 으로 표현할 수 있습니다.(S : 시작위치, E : 끝 위치)

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 모든 웅덩이를 다리로 덮는 최적의 경우를 탐색합니다.

 

3. 최소의 널빤지 개수를 결과로 출력합니다.

 

최적의 널빤지로 다리 만들기

 

널빤지를 최소로 사용하면서 웅덩이를 덮으려면??

 

→ 작은 위치부터 순차대로 널빤지를 덮는다.

 

즉, 웅덩이의 시작위치를 기준으로 끝위치까지 순차대로 웅덩이를 덮으면 됩니다.

 

하지만,

 

널빤지를 덮을 때 해당 웅덩이의 범위를 벗어나는 경우를 신경써주어야 합니다.

 

널빤지의 길이가 5일 때

 

웅덩이가 3이면?

 

ㅡㅡㅡㅡㅡ

 

MMM

 

위와 같이 널빤지가 벗어나는 것도 신경쓰면서 순차대로 웅덩이를 덮으면 최소의 널빤지로 덮을 수 있습니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

N : 3

L : 3

1 6
13 17
8 12

2. 모든 웅덩이를 다리로 덮는 최적의 경우를 탐색합니다.

 

시작 위치를 작은 값부터 웅덩이에 널빤지를 덮기 위해 정렬합니다.

 

1 6

8 12
13 17

 

(1 ~ 6) 웅덩이 덮기

 

→ (1~3), (4~6)까지의 널빤지 2개 추가!

 

(8 ~ 12) 웅덩이 덮기

 

 

→ (8~10), (11~13)까지의 널빤지 2개 추가!

 

(13 ~ 17) 웅덩이 덮기

 

→  13은 이미 덮어져있기 때문에!!! 14부터 덮기를 시작합니다!!

→ (8~10), (11~13)까지의 널빤지 2개 추가!

 

 

3. 최소의 널빤지 개수를 결과로 출력합니다.

 

 

널빤지의 개수 : 5개

 

5 을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 웅덩이와 널빤지의 정보를 저장합니다.
• 웅덩이 위치를 기준으로 PriorityQueue에 정렬되도록 저장합니다.
• 널빤지를 놓는 최적의 경우를 진행합니다.
• 최적의 경우의 널빤지 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

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

public class Main {
    //웅덩이 정보 관련 클래스
    static class Info implements Comparable<Info>{
        int s, e;	//s : 시작값, e : 끝 값
        //기본 생성자
        public Info(int s, int e){
            this.s = s;
            this.e = e;
        }

        //시작값 기준 오름차순 정렬
        //시작값 같으면 끝 값 내림차순 정렬
        @Override
        public int compareTo(Info o) {
            if(this.s == o.s)
                return o.e - this.e;
            return this.s - o.s;
        }
    }
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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());	//널빤지 길이
        PriorityQueue<Info> pq = new PriorityQueue<>();	//정렬하여 사용할 PriorityQueue
        //웅덩이 정보 저장 및 정렬
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            pq.offer(new Info(s, e));
        }
        int result = 0;	//널빤지 개수
        int fill = 0;	//널빤지를 덮은 최대 위치
        //널빤지로 다리 만들기 진행
        while(!pq.isEmpty()){
            Info cur = pq.poll();	//현재 웅덩이
            //현재 웅덩이가 이미 널빤지로 채워진 경우
            if(cur.e < fill)
                continue;

            if(fill < cur.s)	//현재 웅덩이 시작 위치 기준 최대 위치로 변경
                fill = cur.s;

            int remain = (cur.e - fill) % L;	//널빤지 범위 넘어가는 값 구하기
            result += (cur.e - fill) / L;	//사용할 널빤지 개수 구하기
            fill = cur.e;
            //널빤지 범위 넘어갈 때
            if(remain != 0) {
                result++;
                fill += L - remain;
            }

        }
        bw.write(String.valueOf(result));	//널빤지 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}