: 각 구간의 길이 및 해당 구간에서의 제한 속도와 테스트 구간의 길이와 속도를 입력받는다.
해당 구간과 제한 속도를 area 라는 변수에 담아주고, 테스트 구간과 길이를 비교하는 로직이다.
구간 비교
: 여기서 주의해야 할 점은 시작점과 끝점이다. 입력예제 1을 예시로 들어보겠다.
[50, 50] [40, 40] [10, 30] 이 주어졌을 때 해당 구간에 대해서
1-50 : 제한속도 50
51 - 90 : 제한속도 40
91 - 100 : 제한속도 30
로 설정해 주어야 한다. 즉 겹치는 부분이 존재하면 정답이 달라질 수 있다는 것이다.
이 부분만 조심하면 어렵지 않을 것이다. (필자는 이 부분을 놓쳐서 처음에는 틀렸었다!)
✅ 전체 코드
: 깊게 생각하면 어렵지 않은 문제다. 어려운 문제라고, 난이도가 높다고 겁먹지 말고 문제를 천천히 읽어보며
어느 알고리즘 분류에 속하는지, 내가 아는 알고리즘 지식으로 접근할 수 있는지에 대해 고민해보면 어렵지 않을 것이다.
어렵지 않아서 풀 수는 있었지만 더 효율적인 코드가 있다면 댓글로 알려주세요!
import java.util.*;
import java.io.*;
class Main
{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N, M;
static int[] area = new int[101];
static int max;
public static void main(String args[]) throws IOException
{
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int index = 1;
int end, limit;
// 구간별 제한속도 설정
while(N--> 0) {
st = new StringTokenizer(br.readLine(), " ");
end = Integer.parseInt(st.nextToken());
limit = Integer.parseInt(st.nextToken());
end += index + 1;
for(int i=index; i<= end; i++) {
if(i >= 100) break;
area[i] = limit;
}
index = end - 1;
}
index = 1;
while(M-- >0) {
st = new StringTokenizer(br.readLine(), " ");
end = Integer.parseInt(st.nextToken());
limit = Integer.parseInt(st.nextToken());
end += index-1;
for(int i=index; i<= end; i++) {
if(i >= 100) break;
if(area[i] < limit) {
max = Math.max(max, limit-area[i]);
// System.out.println(max);
}
}
index = end + 1;
}
System.out.println(max);
}
}