[Baekjoon] 1449_수리공 항승

Silver III

문제(출처: https://www.acmicpc.net/problem/1449)

---

< 수리공 항승 >

 

문제 풀이 

 

우선순위 큐에 물이 새는 곳의 위치의 좌우 0.5 간격 위치를 넣어준다.

우선순위 큐에서 값을 꺼내며 테이프의 길이를 더했을 때 다음 값까지 테이프를 붙일 수 있는지 없는지 판단하여 테이프의 개수를 구한다.

 

 

 my solution (Java)

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

public class _1449_ { // 수리공 항승

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(bf.readLine());

		PriorityQueue<Double> queue = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(st.nextToken());
			queue.add(x - 0.5);
			queue.add(x + 0.5);
		}

		double temp = queue.poll();
		int result = 1;
		boolean flag = false;

		while (!queue.isEmpty()) {
			if (temp + l > queue.peek()) {
				queue.poll();
			} else if (!flag && temp + l == queue.peek()) {
				flag=true;
				queue.poll();
			} else {
				temp = queue.poll();
				result += 1;
				flag=false;
			}
		}

		System.out.println(result);
	}
}

 

Main

변수)
n : 물이 새는 곳의 개수
l : 테이프의 길이
queue : 우선순위 큐
temp : 우선순위 큐 값
result : 테이프의 개수
flag : 테이프 경계선 위치 여부

 

- 물이 새는 곳의 개수(n), 테이프의 길이(l) 입력

- 물이 새는 곳의 위치를 입력받아 좌우 0.5만큼 간격을 준 값을 우선순위 큐에 저장

- 초기 값을 우선순위 큐에서 꺼냄(temp)

- 우선순위 큐가 빌 때까지 반복

: 현재 위치 + 테이프 길이가 queue의 peek 값 보다 크다면 테이프 하나로 물을 막을 수 있으므로 queue.poll

: 현재 위치 + 테이프 길이가 qeuue의 peek 값과 일치하며 flag 값이 false 라면 여기까지 물을 막을 수 있으므로 flag를 true 표시 및 queue.poll

: 위의 두 가지 경우가 아니라면 테이프로 물을 막을 수 없으므로 temp 값 교체 및 테이프 개수 +1, flag 값을 false로 초기화

- 테이프의 개수(reuslt) 출력

 

* 두 번째 조건에서 flag를 둔 이유는 예를 들어 주어진 예제와 같이 3 2 1이 물이 새는 곳으로 들어오고 테이프의 길이가 1로 주어진다면 우선순위 큐에 0.5 1.5 1.5 2.5 2.5 3.5가 저장될 것이다. 만약 두 번째 조건에서 flag가 없다면 temp가 0.5일 때 1.5가 다 poll 될 것이다. 그럼 다음 temp 값이 2.5가 되고 필요한 테이프의 수가 2가 될 것이다. 이러한 경우를 방지하기 위해 flag를 사용했다.

---

---