https://www.acmicpc.net/problem/1911
1911번: 흙길 보수하기
어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000
www.acmicpc.net
문제
어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.
입력
첫째 줄에 두 정수 N과 L이 들어온다.
둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.
출력
첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.
소스코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
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[][] arr = new int[n][2];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int result = 0;
int pre = -1; // 이전 널빤지 위치
for (int i = 0; i < arr.length; i++) {
// 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우
if(pre >= arr[i][0]) {
// 이전 널빤지 위치가 현재 웅덩이를 덮는 경우
if (pre >= arr[i][1] - 1) continue;
int len = arr[i][1] - pre - 1; // 필요한 널빤지의 길이 (시작위치는 덮어져 있으니까 -1)
if (len % l != 0) {
pre = pre + (len / l) * l + l;
result += len / l + 1;
} else {
pre = arr[i][1];
result += len / l;
}
}
else {
int len = arr[i][1] - arr[i][0]; // 필요한 널빤지의 길이
if (len % l != 0) {
pre = arr[i][0] + (len / l) * l + l - 1; // 시작 위치부터 덮으니까 -1
result += len / l + 1;
} else {
pre = arr[i][1];
result += len / l;
}
}
}
System.out.println(result);
}
}
해결방법
단순히 이전 널빤지의 위치를 보고 아래 두 가지 경우로 나누어 문제를 해결하였다.
1. 이전 널빤지 위치가 현재 웅덩이를 침범하는 경우
2. 이전 널빤지 위치가 현재 웅덩이를 침범하지 않는 경우
'알고리즘 > 백준' 카테고리의 다른 글
14562번 : 태권왕 (0) | 2023.09.28 |
---|---|
9489번 : 사촌 (0) | 2023.09.27 |
5214번 : 환승 (0) | 2023.09.26 |
4889번 : 안정적인 문자열 (0) | 2023.09.25 |
20040번 : 사이클 게임 (0) | 2023.09.22 |