https://www.acmicpc.net/problem/1911
음... 그냥 단순하게 정렬한 후 널빤지의 개수를 구하면 된다.
주의해야 할 건 널빤지의 길이는 정해져 있기 때문에 물웅덩이가 아닌 위치도 널빤지로 덮을 수 있다는 점.
만약 물웅덩이의 위치가 [1,5] [10,15] 이고, 널빤지의 길이가 20이라면 널빤지의 모든 물웅덩이를 커버 가능하다.
이부분만 생각해서 풀면 되는 간단한(?) 문제였다. 딱히 정렬말고 알고리즘을 쓸 필요도 없음...
물웅덩이는 최대 만개이다.
웅덩이의 위치값은 최소 0에서 최대 10억이다.
시간복잡도를 고려하면 범위를 for문으로 돌리면 안된다는 걸 알 수 있다.
import java.io.*;
import java.util.*;
public class Main {
public static int answer = 0;
public static int N,L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
L = Integer.parseInt(st.nextToken());
// 물웅덩이 위치 저장
int[] waters = new int[2*N];
for (int i=0; i<2*N; i+=2) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
waters[i] = start;
waters[i+1] = end;
}
// 정렬해도 상관 없다. 입력에서 물웅덩이 위치가 겹치는 범위는 없으므로
Arrays.sort(waters);
// 널빤지의 가장 마지막 위치를 기억한다.
int lastIdx = 0;
for (int i=0; i<2*N; i+=2) {
int start = waters[i];
이미 물웅덩이에 널빤지가 존재한다면,
시작점을 널빤지의 가장 마지막 위치 + 1로 잡는다.
if (lastIdx >= start) {
start = lastIdx + 1;
}
int end = waters[i+1];
int length = end - start;
// 이미 널빤지가 대져있을 수도 있기 때문에, 이런 경우는 continue
if (length <= 0) continue;
// 널빤지 개수
int cnt = length/L;
// 널빤지 대고 남는 부분
int res = length%L;
// 남는 부분이 있으면, 널빤지개수를 1 증가시키고 마지막 널빤지위치를 구한다.
if (res != 0) {
cnt++;
lastIdx = waters[i+1]-1 + (L - res);
}
// 답에 카운트 더하기
answer += cnt;
}
System.out.println(answer);
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
| 백준 오아시스 재결합 3015 자바 (0) | 2024.07.04 |
|---|---|
| 백준 소수의 연속합 1644 자바 (0) | 2024.07.04 |
| 백준 1202 파이썬 보석 도둑 (0) | 2022.01.23 |
| 백준 2109 파이썬 순회공연 (0) | 2022.01.23 |
| 백준 1285 동전 뒤집기 파이썬 (0) | 2022.01.23 |
