이번 문제는 백준의 골드 5 문제인 흙길 보수하기 문제이다.
문제를 차근차근 읽어보자.
널빤지의 길이와 구덩이가 주어지는데, 필요한 널빤지의 수를 묻는다.
어떻게 구덩이를 메꿔야 최소 널빤지만을 이용할 수 있을까?
먼저 문제의 제약 조건부터 파악해보자.
널빤지의 최대길이가 10만이며, 구덩이의 위치는 최대 10억이다.
이를 보았을 때, 자료형은 long long을 사용함이 좋아보인다.
또한, 나는 이런 문제를 보게되면 입력을 어디에 저장할지 먼저 고민한다.
웅덩이의 위치가 주어졌는데, 어디에 저장했다 사용을 해야할까?
나는 벡터에 둘 다 저장하고, 이후에 꺼내서 사용하도록 결정했다.
불필요하게 배열을 크게 만들 필요도 없고, 정렬하기도 간편하기 때문이다.
그럼 이제 문제를 어떤 식으로 풀어나가야 할까?
완전 탐색?
널빤지를 까는 모든 경우를 다 탐색하는 완전탐색일까?
얼마나 걸릴 지 한 번 생각해보자.
웅덩이는 최대 10000개가 존재할 수 있다.
심지어 널빤지는 길이가 최소 1이고 웅덩이는 10억까지 위치할 수 있다.
이 때, 널빤지를 웅덩이에 설치하는 모든 경우를 다 탐색한다는 것은
시간이 말도 안되게 오래 걸리는 일임을 직감할 수 있다.
최소 널빤지를 사용하여 모든 웅덩이를 채우도록 한다.
과연 어떻게 널빤지를 깔아야 최소로 사용할 수 있을까?
이 말을 한 순간, 이 문제는 Greedy 알고리즘 문제가 된다.
Greedy 문제
완전 탐색으로는 풀 수 없으니, 널빤지가 최소로 사용될 수 밖에 없는
상황을 부여하여 해당 조건하에서 사용되는 널빤지의 수를 구한다.
이를 우리는 Greedy 문제라고 부른다.
우선 우리는 웅덩이의 위치를 알고 있다.
웅덩이를 탐색하기 편하게 시작 위치 기준으로 정렬을 한 번 해보자.
이후, 가장 앞 웅덩이부터 그냥 차례로 널빤지를 한 번 깔아보자.
이 때, 1차원 배열로 가상의 길을 구현해 널빤지의 위치를 표시한다.
과연 그냥 앞에서부터 차례차례 깔았을 때, 어떻게 될까?
#define ll long long
ll num = 0, wood_len = 0, answer = 0, last_pit_pos = 0;
vector<pair<ll, ll>> pit_list;
int main(){
cin >> num >> wood_len;
for (int i = 0; i < num; i++) {
ll from = 0;
ll to = 0;
cin >> from >> to;
pit_list.push_back({from, to});
last_pit_pos = max(to, last_pit_pos);
}
vector<bool> check_road(last_pit_pos + wood_len, false);
// 메모리 초과 방지를 위해, 마지막 위치 + 나무 길이만큼 배열 할당
sort(pit_list.begin(), pit_list.end());
for (int i = 0; i < num; i++) {
ll from = pit_list[i].first;
ll to = pit_list[i].second;
for (int j = from; j < to; j++) {
if (!check_road[j]) {
// 웅덩이면, 길이만큼 널빤지를 깐다.
for (int k = j; k < j + wood_len; k++)
check_road[k] = true;
j += (wood_len - 1); // j를 길이만큼 증가시켜주자.
answer++; // 여기에 들어올 때마다 널빤지 갯수 증가
}
} // 증가된 j가 길을 벗어났으면, 알아서 종료될 것이다.
}
cout << answer;
return 0;
}예제에 대한 답은 나왔지만 아쉽게도 시간 초과가 발생했다.
내가 지금 사용한 방식은 3중 for문이다.
아무래도 완전 탐색만큼은 아니겠지만, 시간이 꽤 걸리는 모양이다.
분명 앞에서 부터 널빤지를 깔아 나간다는 아이디어는 맞는 것 같다.
보다 단순한 과정을 통해서 널빤지의 수를 구할 순 없을까?
지금 깐 널빤지가 다음 구덩이까지 걸쳐지는 경우를 어떻게 해결할까?
#define ll long long
ll num = 0, wood_len = 0, answer = 0;
vector<pair<ll, ll>> pit_list;
int main(){
cin >> num >> wood_len;
for (int i = 0; i < num; i++) {
ll from = 0;
ll to = 0;
cin >> from >> to;
pit_list.push_back({from, to});
}
sort(pit_list.begin(), pit_list.end());
ll wood_positon = 0;
for (int i = 0; i < num; i++) {
ll from = pit_list[i].first;
ll to = pit_list[i].second;
if (from > wood_positon)
wood_positon = from;
// 나무 위치를 시작지점에 가져다 놓자.
while (to > wood_positon) {
wood_positon += wood_len;
answer++;
}
// 나무의 위치가 웅덩이의 끝을 넘을 때 까지 설치한다.
// 이 때, 다른 웅덩이에 걸치면, from으로 갱신되지 않는다.
}
cout << answer;
return 0;
}생각보다 해답은 간단했다.
내가 구현했던 구덩이를 덮는 과정은 덧셈 문장 하나로 대체되었다.
또한 핵심은, 널빤지의 마지막 위치를 계속 추적한다는 점이다.
그럼 다른 웅덩이에 걸쳐진 상태에서도 계산이 가능하다.
왜? 웅덩이의 시작 위치가 아닌, 널빤지의 마지막 위치부터
다음 계산을 진행하게 되기 때문이다.