[백준_1449번] 수리공 항승

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

1449번: 수리공 항승

[문제]

 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

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

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

 

[입력 조건]

 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1449 {
	// 처음 누수 지점을 무조건 테이프를 붙여야하기 떄문에 count는 1로 초기화
	public static int n,l,count=1;
	public static ArrayList<Integer> position=new ArrayList<Integer>();
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		l=sc.nextInt();
		
		for(int i=0;i<n;i++)
			position.add(sc.nextInt());
		
		// 입력받은 위치를 정렬
		Collections.sort(position);
		
		int prev=position.remove(0); // 이전의 위치

		while(!position.isEmpty()) {
			int current=position.remove(0); // 현재 위치
			
			/*
			 * 두 위치의 거리 차가 하나의 테이프로 커버 가능하다면
			 * 개수를 증가시키지 않고 넘어간다.
			 * 이때 prev는 갱신시키지 않아야 한다.
			 * 
			 * 예를 들어 1 2 3 101 102 지점에서 누수가 일어났다면
			 * 1-2 지점은 if문을 만족하므로 count 하지 않지만 prev는 1이기 때문에
			 * 다름 3 지점에서는 3-1=2는 아래 if 문을 만족하지 않기 때문에 
			 * count 증가하고 prev를 갱신시켜준다.
			 */
			if(current-prev<=l-1) 
				continue;
				
			prev=current; // prev 갱신
			count++; // 테이프 수 count
		}
		System.out.println(count);
	}

}

 

[고찰]

 이번 문제는 이전 파이프의 위치를 언제 갱신해주냐가 중요한 문제였다. 이전 파이프의 위치는 앞뒤의 누수 위치를 뺀 값이 테이프의 길이-1 보다 큰 경우에 갱신시켜야 한다. 반대의 경우에 갱신시키면 1 2 3 세 곳에서 누수가 일어난 경우 테이프의 개수가 1개밖에 count 되지 않게 된다. 1-2 지점은 1개의 테이프로 커버가 가능하기 때문에 테이프의 개수를 count 하지 않아야 하지만 다음 지점인 3은 테이프가 필요하기 때문에 prev를 갱신하지 않고 1로 둔다면 3-1=2로 1보다 크기 때문에 테이프의 개수가 증가하게 된다. 

 이해하고 보면 쉬운 문제였지만 이런 방법을 떠올리기까지는 시간이 쫌 걸렸던 문제였다.