이번에는 백준 1911번 흙길 보수하기 문제를 풀어보았습니다.
여러 개의 물웅덩이를 일정한 길이의 널빤지로 모두 덮어야 하며, 필요한 널빤지의 최소 개수를 구해야 합니다.
물웅덩이를 시작 위치 기준으로 정렬한 뒤, 이전에 설치한 널빤지가 어디까지 덮고 있는지를 관리하는 그리디 알고리즘으로 해결하였습니다.
문제 설명
흙길 위에 N개의 물웅덩이가 있습니다.
각 물웅덩이는 시작 위치와 끝 위치로 주어지며, 길이가 L인 널빤지를 사용하여 모든 물웅덩이를 덮어야 합니다.
널빤지는 충분히 많이 가지고 있으며, 필요한 널빤지의 최소 개수를 구해야 합니다.
이전에 설치한 널빤지가 다음 물웅덩이의 일부 또는 전체를 덮을 수도 있으므로, 이미 덮은 범위를 함께 고려해야 합니다.
풀이 아이디어
물웅덩이를 시작 위치 기준으로 오름차순 정렬합니다.
이후 왼쪽에 있는 물웅덩이부터 차례대로 처리합니다.
ed에는 이전까지 설치한 널빤지가 덮고 있는 가장 오른쪽 위치를 저장합니다.
현재 물웅덩이를 확인할 때는 다음 세 가지 경우로 나눌 수 있습니다.
- 이전 널빤지가 현재 물웅덩이 전체를 이미 덮은 경우
- 이전 널빤지와 현재 물웅덩이가 떨어져 있는 경우
- 이전 널빤지가 현재 물웅덩이의 일부를 덮은 경우
현재 물웅덩이에서 아직 덮이지 않은 길이를 구한 뒤, 해당 길이를 덮기 위해 필요한 널빤지 개수를 올림 계산합니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> inp;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N,L;
cin >> N >> L;
for (int i=0; i<N; i++) {
int st,ed;
cin >> st >> ed;
inp.push_back({st,ed});
}
sort(inp.begin(), inp.end());
int ret = 0;
int st =0, ed=0;
for (pair<int, int> curr : inp) {
int cnt = 0;
if (ed >= curr.second) continue;
if (ed < curr.first) {
st = curr.first;
} else {
st = ed;
}
ed = curr.second;
cnt += (ed-st)/L;
if ((ed-st)%L) cnt+=1;
ret += cnt;
ed = st + L * cnt;
}
cout << ret;
return 0;
}풀이 흐름
-
물웅덩이의 시작 위치와 끝 위치를 입력받습니다.
-
물웅덩이를 시작 위치 기준으로 오름차순 정렬합니다.
-
이전까지 설치한 널빤지가 덮은 끝 위치를
ed에 저장합니다. -
현재 물웅덩이 전체가 이미 덮여 있다면 넘어갑니다.
-
현재 물웅덩이가 이전 널빤지와 떨어져 있다면 물웅덩이의 시작 위치부터 덮습니다.
-
이전 널빤지가 현재 물웅덩이 일부를 덮고 있다면 기존에 덮은 끝 위치부터 이어서 덮습니다.
-
아직 덮어야 하는 길이를 기준으로 필요한 널빤지 개수를 계산합니다.
-
사용한 널빤지 개수를 정답에 더합니다.
-
새롭게 설치한 널빤지가 덮는 끝 위치를 갱신합니다.
-
모든 물웅덩이를 처리한 뒤 널빤지의 최소 개수를 출력합니다.
구현 포인트
1. 물웅덩이 정렬
sort(inp.begin(), inp.end());pair<int, int>는 기본적으로 첫 번째 값을 기준으로 정렬되고, 첫 번째 값이 같다면 두 번째 값을 기준으로 정렬됩니다.
따라서 물웅덩이가 시작 위치를 기준으로 오름차순 정렬됩니다.
왼쪽에 있는 물웅덩이부터 처리해야 이전에 설치한 널빤지가 다음 물웅덩이를 얼마나 덮었는지 연속적으로 확인할 수 있습니다.
2. ed가 의미하는 값
int st =0, ed=0;반복문이 시작되기 전 ed는 아직 어떤 위치도 덮지 않았다는 의미로 0으로 초기화됩니다.
반복문이 진행되는 동안 ed는 이전까지 설치한 널빤지가 덮고 있는 가장 오른쪽 위치를 의미합니다.
예를 들어 길이가 3인 널빤지를 위치 2부터 두 개 설치했다면 다음 범위를 덮습니다.
[2, 5)
[5, 8)이 경우 ed는 8이 됩니다.
다음 물웅덩이를 처리할 때 8 이전의 구간은 이미 덮였다고 판단할 수 있습니다.
3. 이미 물웅덩이 전체가 덮인 경우
if (ed >= curr.second) continue;이전에 설치한 널빤지가 현재 물웅덩이의 끝 위치 이상까지 덮고 있다면 현재 물웅덩이는 이미 전부 처리된 상태입니다.
예를 들어 이전 널빤지가 위치 10까지 덮고 있고, 현재 물웅덩이가 [6, 9)라면 널빤지를 추가할 필요가 없습니다.
따라서 현재 물웅덩이를 건너뜁니다.
이 조건이 없다면 이후 계산에서
ed - st가 음수가 되거나, 이미 덮인 물웅덩이에 널빤지를 추가하는 오류가 발생할 수 있습니다.
4. 이전 널빤지와 현재 물웅덩이가 떨어진 경우
if (ed < curr.first) {
st = curr.first;
}이전에 덮은 끝 위치 ed가 현재 물웅덩이의 시작 위치보다 작다면 두 구간 사이가 떨어져 있다는 의미입니다.
예를 들어 이전 널빤지가 위치 5까지 덮었고 현재 물웅덩이가 위치 8에서 시작한다면, 위치 5부터 8까지는 덮을 필요가 없습니다.
따라서 현재 물웅덩이의 시작 위치인 curr.first부터 널빤지를 설치합니다.
5. 이전 널빤지가 현재 웅덩이 일부를 덮은 경우
else {
st = ed;
}ed가 현재 물웅덩이의 시작 위치 이상이라면, 이전에 설치한 널빤지가 현재 물웅덩이의 앞부분까지 이미 덮고 있다는 뜻입니다.
예를 들어 현재 물웅덩이가 [5, 12)이고 이전 널빤지가 위치 8까지 덮고 있다면 [5, 8) 구간은 이미 처리된 상태입니다.
따라서 남은 구간인 [8, 12)만 덮으면 됩니다.
이 경우 널빤지를 설치할 시작 위치 st를 기존의 ed로 설정합니다.
6. 현재 물웅덩이의 끝 위치 저장
ed = curr.second;st를 결정한 뒤 현재 물웅덩이의 끝 위치를 ed에 저장합니다.
이 시점에서는 다음 구간을 덮어야 합니다.
[st, ed)이 구간의 길이는 다음과 같습니다.
ed - st7. 필요한 널빤지 개수 계산
cnt += (ed-st)/L;
if ((ed-st)%L) cnt+=1;현재 남은 물웅덩이 길이는 ed - st입니다.
이를 널빤지 길이 L로 나누어 필요한 개수를 구합니다.
나누어떨어진다면 몫만큼의 널빤지가 필요합니다.
예를 들어 길이 6인 구간을 길이 3의 널빤지로 덮는다면 다음과 같습니다.
6 / 3 = 2널빤지 두 개면 정확히 덮을 수 있습니다.
반면 나머지가 존재한다면 널빤지 하나가 추가로 필요합니다.
예를 들어 길이 7인 구간을 길이 3의 널빤지로 덮는다면 다음과 같습니다.
7 / 3 = 2, 나머지 1널빤지 두 개로는 길이 6까지만 덮을 수 있으므로 하나를 더 사용해야 합니다.
따라서 총 세 개가 필요합니다.
8. 올림 계산
현재 코드의 다음 부분은 나눗셈 결과를 올림하는 역할을 합니다.
cnt += (ed-st)/L;
if ((ed-st)%L) cnt+=1;수식으로 표현하면 다음과 같습니다.
ceil((ed - st) / L)널빤지는 일부만 사용할 수 없으므로 남은 길이가 널빤지 길이의 배수가 아니라면 반드시 한 개를 더 설치해야 합니다.
9. 전체 널빤지 개수 갱신
ret += cnt;현재 물웅덩이에서 추가로 설치한 널빤지의 개수를 전체 개수에 더합니다.
ret에는 지금까지 모든 물웅덩이를 덮기 위해 사용한 널빤지의 개수가 저장됩니다.
10. 널빤지가 실제로 덮은 끝 위치 갱신
ed = st + L * cnt;널빤지는 현재 물웅덩이의 끝에 정확히 맞춰서 끝나지 않을 수도 있습니다.
예를 들어 현재 덮어야 하는 구간이 [2, 8)이고 널빤지 길이가 4라면 두 개의 널빤지를 사용합니다.
첫 번째 널빤지: [2, 6)
두 번째 널빤지: [6, 10)물웅덩이는 위치 8에서 끝나지만 실제 널빤지는 위치 10까지 덮게 됩니다.
따라서 단순히 현재 물웅덩이의 끝 위치를 저장하는 것이 아니라, 널빤지가 실제로 덮은 끝 위치를 저장해야 합니다.
st + L × cnt이렇게 저장한 ed는 다음 물웅덩이를 일부 또는 전체 덮을 수 있습니다.
11. 그리디하게 널빤지를 배치하는 이유
현재 물웅덩이에서 아직 덮이지 않은 가장 왼쪽 위치부터 널빤지를 설치합니다.
널빤지를 더 왼쪽에 설치하면 이미 덮인 구간을 다시 덮게 되므로 낭비가 발생합니다.
반대로 현재 필요한 가장 왼쪽 위치보다 오른쪽에 설치하면 물웅덩이의 일부가 덮이지 않습니다.
따라서 아직 덮이지 않은 가장 왼쪽 지점부터 널빤지를 이어서 설치하는 것이 가장 효율적입니다.
또한 널빤지가 물웅덩이 끝을 넘어가더라도 그 범위는 다음 물웅덩이를 덮는 데 사용할 수 있으므로 그대로 유지합니다.
12. 예시 흐름
널빤지 길이가 3이고 다음 물웅덩이가 있다고 가정합니다.
[1, 5)
[6, 8)첫 번째 물웅덩이의 길이는 4입니다.
따라서 널빤지 두 개가 필요합니다.
[1, 4)
[4, 7)첫 번째 물웅덩이는 위치 5에서 끝나지만 널빤지는 위치 7까지 덮습니다.
다음 물웅덩이는 [6, 8)이므로 [6, 7) 구간은 이미 덮여 있습니다.
따라서 위치 7부터 널빤지 하나만 추가하면 됩니다.
[7, 10)이처럼 이전 널빤지가 덮은 범위를 유지하면 필요한 널빤지의 최소 개수를 구할 수 있습니다.
시간복잡도
물웅덩이 N개를 정렬하는 데 필요한 시간복잡도는 다음과 같습니다.
O(N log N)정렬 후 모든 물웅덩이를 한 번씩 순회하므로 O(N)이 추가로 필요합니다.
따라서 전체 시간복잡도는 다음과 같습니다.
O(N log N)N은 최대 10,000이므로 충분히 해결할 수 있습니다.
