[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1449번, 수리공 항승

문제 링크

1449번: 수리공 항승

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

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

2. 테이프로 물을 막을 때 앞 뒤로 0.5만큼 더 붙여야 물이 새는 것을 막을 수 있습니다.

3. 파이프의 구멍을 모두 막는데 최소로 사용하는 테이프의 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 구멍의 위치를 오름차순 정렬한 뒤, 테이프를 붙이는 최상의 선택을 진행합니다.

 

3. 테이프를 붙인 횟수를 결과로 출력합니다. 

 

 

테이프 붙이기.

 

오름차순으로 정렬된 구멍이 존재할 때,

 

낮은 구멍의 위치를 시작으로 테이프를 순차적으로 붙입니다.

 

테이프를 붙일 때 현재까지 테이프가 붙인 최대 구역을 저장하여 다음 구멍이 최대 구역보다 작으면 테이프로 이미 보완한 것으로 판단할 수 있습니다.

 

예를들어L : 5일 때

6

8

12

16

25

낮은 구멍에 테이프 붙이기!

6(테이프 붙이기)

8

12

16

25

5.5 ~ 10.5까지 붙이기 됩니다.

최대 구역 : 10

 

다음 구멍(8) 확인!

다음 구멍은 8 ≤ 10(최대 구역)이 만족하기 때문에 이미 테이프로 물이 새는 것을 막았습니다.

 

다음 구멍(12) 확인!

다음 구멍은 8 ≤ 10(최대 구역)이 만족하기 않아서 테이프를 붙여야 합니다.

6

8

12(테이프 붙이기)

16

25

11.5 ~ 16.5까지 붙이기 됩니다.

최대 구역 : 16

 

다음 구멍(16) 확인!

다음 구멍은 16 ≤ 16(최대 구역)이 만족하기 때문에 이미 테이프로 물이 새는 것을 막았습니다.

 

다음 구멍(25) 확인!

다음 구멍은 25 ≤ 16(최대 구역)이 만족하기 않아서 테이프를 붙여야 합니다.

6

8

12

16

25(테이프 붙이기)

24.5 ~ 30.5까지 붙이기 됩니다.

최대 구역 : 30

테이프를 붙인 횟수 : 3번

 

여기서 찾아볼 수 있는 것은 테이프를 붙일 때 -0.5 ~ +0.5를 진행해야 하기 때문에최대구역 = 시작위치 + (L-1)  구역을 이동하는 것을 확인할 수 있습니다.

 

예제입력 3.

 

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

 

N : 3

L : 1

 

Pipe

3

2

1

 

2. 구멍의 위치를 오름차순 정렬한 뒤, 테이프를 붙이는 최상의 선택을 진행합니다.

 

오름차순 정렬!

1

2

3

 

가장 작은 구멍부터 테이프 붙이기!

1(테이프 붙이기)

2

3

0.5 ~ 1.5까지 붙이기 됩니다.

최대 구역 : 1

 

다음 구멍(2) 확인

다음 구멍은 2≤ 1(최대 구역)이 만족하기 않아서 테이프를 붙여야 합니다.

1

2(테이프 붙이기)

3

1.5 ~ 2.5까지 붙이기 됩니다.

최대 구역 : 2

 

다음 구멍(3) 확인

다음 구멍은 3 ≤ 2(최대 구역)이 만족하기 않아서 테이프를 붙여야 합니다.

1

2

3(테이프 붙이기)

2.5 ~ 3.5까지 붙이기 됩니다.

최대 구역 : 3

 

3. 테이프를 붙인 횟수를 결과로 출력합니다. 

 

테이프를 붙인 횟수 : 3번(1, 2, 3)

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 사용하여 문제의 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort로 파이프 구멍에 따른 오름차순 정렬을 하였습니다.
• 각 구멍이 최대 구역에 맞게 테이프로 막았습니다.
• 테이프로 막은 횟수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    static int N,L,C, answer = 1;
    static int[] pipe;	//파이프 구멍 정보 배열
    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()," ");
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        pipe = new int[N];
        //파이프 구멍 정보 저장
        for(int i=0;i<N;i++)
            pipe[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(pipe);	//파이프 오름차순 정렬
        C = pipe[0] + (L-1);	//시작에서 가장 가까운 구멍 막기 및 최대 구역 설정
        //각 구멍들 확인해보며 테이프 붙일지 확인
        for(int i = 1;i<N;i++){
            if(pipe[i] <= C)	//이미 파이프 구멍이 테이프로 막혔을 때
                continue;
            C = pipe[i] + (L-1);		//최대 구역보다 커서 새로 테이프를 붙일 때
            answer++;
        }
        bw.write(answer + "");	//테이프 붙인 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}