백준 1499번) 수리공 항승 JAVA

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

1449번: 수리공 항승

 

#문제

 

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

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

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

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

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

 

#알고리즘

그리디, 정렬

 

#난이도

SILVER3

 

#풀이방법

내가 개인적으로 재밌어하는 부분인 그리디,정렬 문제이다.

사실 이런 문제 자체가 그리디문제의 대표적이고 핵심적인 유형이 아닐까 생각된다. 

풀이 방법은 간단하다. 구멍이 뚫린 곳을 오름차순으로 정렬 한 후

오름차순으로 구멍이 뚫린 곳을 테이프로 부착시켜 매꾸고 count++ 

그 다음 구멍이 뚫린 곳을 찾아 테이프를 그리디적으로 붙이고 개수를 세서 print하면 된다.

 

필자의 경우 Arrays.sort를 써서 정렬을 하기보다는 visited boolean 1차원 배열을 선언하여

구멍이 뚫린 곳을 true로 선언하고, visited를 for문으로 순서대로 탐색하여

index가 true인 곳이 있으면 테이프를 붙여 테이프의 시작점 부터 끝점까지의 구멍이 뚫린 곳이 있다면

전부 매꾸고, count+1, 또 그다음 구멍이 뚫린 곳이 있다면 이전의 방법대로 탐색하여 구멍이 뚫린 곳을 매꾸어준다.

 

 

#코드

import java.util.*;
//1t

public class Main {

	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		
		int count = 0;
		int N = sc.nextInt();
		int L = sc.nextInt();
		
		int[] leak = new int[N];
		boolean[] visited = new boolean[1001];
		
		for(int i=0; i<leak.length; i++)
			leak[i] = sc.nextInt();
		
		for(int i=0; i<leak.length; i++) {
			visited[leak[i]] = true;
		}
		
		for(int i=0; i<visited.length; i++) {
			
			if(visited[i]) {
				
				for(int j=i; j<i+L&&j<visited.length; j++) {
					if(visited[j]) {
						visited[j] = false;
					}
				}
				count++;
			}
			
		}
		
		System.out.println(count);
		
		

	}

}