#1449 : 수리공 항승

풀이방법

사용된 것:

그리디 알고리즘

정렬

 

2022.04.28

물이 새는 곳을 편하게 '구멍'이라 부르겠다.

 

가장 왼쪽 구멍부터 살피면 되므로 그리디 알고리즘이다.

가장 왼쪽 구멍부터 살피려면 구멍 위치 배열을 오름차순 정렬해야 하므로 정렬이 사용된다.

 

먼저 구멍들의 위치를 싹 읽어와 int[]형 배열에 저장한 뒤, 이 배열을 오름차순 정렬한다.

 

2개의 정수형 변수가 사용된다.

1. 정수형 변수 cnt는 현재까지 사용된 테이프의 개수를 저장한다. 즉, 다 풀고 나면 이 문제의 정답이 cnt에 저장되게 된다. 다 쓰지 않았더라도 지금 사용하는 중인 테이프까지 세어야 하므로 초기값을 0이 아닌 1로 선언한 뒤, 새 테이프를 꺼낼 때마다 1씩 증가시킬 것이다.
2. 정수형 변수 left는 지금 사용하는 중인 테이프의 왼쪽 끝이 붙여진 위치이다.

 

가장 왼쪽 구멍부터 오른쪽으로 차근차근 진행한다.

일단 가장 왼쪽 구멍에 테이프의 왼쪽 끝을 붙인다. 즉 left의 값을 가장 왼쪽 구멍의 위치로 한다.

 

다음 구멍으로 넘어간다.

 

그리고 아래의 과정을 모든 구멍에 대하여 수행하면 문제가 해결된다.

 

구멍의 위치에서 left의 값을 뺀다.

1. 이 값이 테이프의 길이보다 작다면, 같은 테이프로 커버할 수 있는 것이다. 아무런 조치를 취하지 않고 다음 구멍으로 넘어간다.
2. 이 값이 테이프의 길이보다 크거나 같다면, 쓰던 테이프로 커버하지 못할 정도로 먼 것이다. 새 테이프를 꺼내야 한다. cnt를 1 증가시키고 left를 이번 구멍의 위치로 변경한 뒤, 다음 구멍으로 넘어간다.

 

 

구멍의 위치에서 left를 뺀 값이 테이프 길이를 초과했을 때가 아니라 이상일 때에 새 테이프를 꺼내는 것은 좌우 0.5cm의 여유공간 때문이다.

좌우 0.5cm, 즉 1cm의 여유공간을 고려하지 않았다면 테이프의 길이를 초과했을 때에만 새 테이프를 꺼냈을 것이다.

하지만 여유공간을 고려해서 1cm는 없는 셈 쳐야 하므로 초과가 아닌 이상일 때 새 테이프를 꺼낸다.

 

코드

Java(2022.04.28)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//데이터 읽어오기
		int n = Integer.parseInt(st.nextToken());	//구멍 개수
		int l = Integer.parseInt(st.nextToken());	//테이프 길이
		int[] holes = new int[n];	//구멍 위치 배열
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			holes[i] = Integer.parseInt(st.nextToken());
		}
		
		//구멍 위치 오름차순 정렬
		Arrays.sort(holes);
		
		//정답 구하기
		int cnt = 1;	//지금까지 쓴 테이프의 개수(현재 사용중인 테이프를 포함하므로 초기값은 1)
		int left = holes[0];	//현재 사용중인 테이프의 왼쪽 끝 위치
		for(int i = 1; i<n; i++) {
			
			//이번 구멍이 너무 먼 경우
			if(holes[i]-left >= l) {
				cnt++;		//테이프 하나 더 사용
				left = holes[i];//새 테이프의 왼쪽 끝 위치 갱신
			}
			
			//쓰던 테이프를 계속 쓸 수 있는 경우 그냥 진행
		}
		
		System.out.print(cnt);

	}

}