[Java] 백준 1449번 (수리공 항승)

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

1449번: 수리공 항승

 

알고리즘 분류

• 그리디
• 정렬

 

풀이

그리디 알고리즘을 사용해 풀었다. 

핵심 로직은 이러하다.

 

먼저 StringTokenizer로 물이 세는 곳을 저장한뒤,

새는 곳이 차례대로 있어야 최소한의 테이프를 쓰게 되니 정렬까지 진행했다.

st = new StringTokenizer(br.readLine());
for (int i = 0; i < temp.length; i++) {
	temp[i] = Integer.parseInt(st.nextToken());
} // for
		
Arrays.sort(temp);

 

 

 

만약 현재 붙인 테이프 길이가 물이 새는 거리보다 길면 지나가고 

만약 그러지 않으면 (짧다면) 그 새는 곳부터 다시 길이를 재고 테이프의 수량을 하나 늘린다.

for (int i = 0; i < temp.length; i++) {
			
	if(length >= temp[i]) continue;
	else {
		length = temp[i] + l - 1;
		cnt++;
		}	
} // for

 

 

 

아래는 전체 정답 코드이다. 

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

public class Main {
	public static void main(String[] args) throws IOException {
		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 [] temp = new int [n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < temp.length; i++) {
			temp[i] = Integer.parseInt(st.nextToken());
		} // for
		
		Arrays.sort(temp); // 거리가 순서대로 있어야 최소한의 테이프가 필요하므로 정렬
		int cnt = 0; // 테이프 수량
		int length = 0; // 현재 붙인 테이프의 길이
		
		for (int i = 0; i < temp.length; i++) {
			
			if(length >= temp[i]) continue;
			else {
				length = temp[i] + l - 1;
				cnt++;
			}
			
		} // for

		System.out.println(cnt);
	}
}