[Baekjoon] 11971_속도 위반

Silver V

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

---

< 속도위반 >

 

문제 풀이 

 

도로의 구간과 제한속도와 연정이가 달린 구간과 도로 구간을 비교하여 속도위반을 찾는다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _11971_ { // 속도 위반

	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 m = Integer.parseInt(st.nextToken());

		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			queue.add(new int[] { Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) });
		}

		int result = 0;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());

			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());

			while (d > 0) {
				if (queue.peek()[1] < s) {
					result = Math.max(result, s - queue.peek()[1]);
				}
				if (queue.peek()[0] > d) {
					queue.peek()[0] -= d;
					break;
				} else {
					d -= queue.poll()[0];
				}
			}
		}
		System.out.println(result);
	}
}

변수)
n, m : 도로 구간 수, 달린 구간 수
queue : Queue <int []>
result : 속도 위반한 최댓값
d, s : 달린 구간의 길이, 해당 구간에서 달린 속도

 

도로 구간 수와 달린 구간 수를 입력받는다. 도로 구간 길이와 해당 구간의 제한 속도를 입력받아 queue에 저장한다. 달린 구간 길이와 해당 구간에서 달린 속도를 입력받아 달린 구간의 길이가 0보다 클 때 다음 과정을 계속해서 반복한다.

 

1) queue의 peek 값의 제한속도가 달린 속도보다 작다면 속도 위반한 것이므로 result를 업데이트한다.

2) queue의 peek 값의 도로 구간이 달린 구간 길이보다 크다면 달린 구간만큼 값을 빼준 후 다음 달린 구간을 입력받기 위해 종료한다.

3) queue의 peek 값의 도로 구간이 달린 구간 길이보다 작다면 달린 구간 길이에서 queue에서 poll 한 값의 도로 구간을 빼준다.

 

최종 속도 위반한 최댓값인 result를 출력한다.

---

---