이번 문제는, 백준의 골드 5 꿀 따기 문제이다.
문제부터 차근차근 읽고 파악해보자.
벌 두 마리와 꿀통을 위치시켜, 꿀의 최대치를 구하는 문제이다.
문제의 제약 조건이 위와 같은 것을 보니, 별다른 제약이 없는 듯 하다.
과연 이 문제를 어떤 방식으로 풀어야 할까?
완전 탐색?
먼저, 가장 먼저 생각해볼 수 있는 것은 완전 탐색이다.
3개의 물체를 배열에 위치시킬 수 있는 경우의 수를 모두 훑는다.
또한, 모든 경우의 수마다 얻게될 꿀을 계산하여 비교한다.
그럼 어느 정도의 시간이 걸릴까?
위의 제한에서 배열의 최대 크기는 10만이었다.
그럼 10만 칸 중 3칸을 모두 탐색하고 계산해야 한다는 말이다.
10만 칸 중 서로 다른 3개를 고르면, 100000C3의 조합이 된다.
이는 얼추 계산해보아도 매우 큰 수이므로, 시간초과를 피할 수 없다.
그럼 모두 탐색을 진행하면 문제를 풀 수 없다.
그 말인 즉, 우리는 특정 조건을 걸어 최대로 꿀을 얻도록 해야 한다.
우리는 이를 Greedy 알고리즘이라고 부른다.
어떤 조건 하에서 문제를 풀어야 빠르게 찾을 수 있을까?
이제 문제는 Greedy로
어차피 최대가 되려면, 최대한 많은 꿀을 지나야 할 것이다.
왜? 해당 문제에서 꿀은 음수가 없다. 지나면 반드시 이득이다.
따라서 우리는, 각 개체를 최대한 멀리 떨어트려 놓을 필요가 있다.
그런데, 개체는 3가지 종류다. 어떻게 최대한 멀리 떨어트려놓지?
세 가지 경우로 구분해서 생각해보자.
- 꿀벌을 양 쪽 끝으로 멀리 보내는 경우
- 꿀벌 하나를 왼쪽 끝, 꿀통을 오른쪽 끝에 두는 경우
- 꿀벌 하나를 오른쪽 끝, 꿀통을 왼쪽 끝에 두는 경우
어? 그냥 양 끝에 두고 가운데 두는게 제일 먼 거 아닌가요?
벌이 시작한 자리는 꿀을 먹을 수 없기 때문에, 다 해봐야 한다.
세 가지 경우에 대해서 가운데에 있는 개체를 옮기며 최대를 찾아보자.
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀벌 - 꿀통 - 꿀벌 고정
for (int j = 1; j <= i; j++)
sum += fields[j]; // 꿀벌 1
for (int j = num - 2; j >= i; j--)
sum += fields[j]; // 꿀벌 2
answer = max(answer, sum);
}
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀벌 - 꿀벌 - 꿀통
for (int j = 1; j < num; j++)
if (j != i)
sum += fields[j]; // 꿀벌 1
// 중간에 배치한 꿀벌2의 자리 제외 더하기
for (int j = i + 1; j < num; j++)
sum += fields[j]; // 꿀벌 2
answer = max(answer, sum);
}
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀통 - 꿀벌 - 꿀벌
// 꿀벌 자리는 합에 포함 X
for (int j = num - 2; j >= 0; j--)
if (j != i)
sum += fields[j]; // 꿀벌 1
for (int j = i - 1; j >= 0; j--)
sum += fields[j]; // 꿀벌 2
answer = max(answer, sum);
}하지만 이 풀이는 시간 초과를 받게 되었다.
아무래도 이중 for문을 돌리기에는 10만 칸은 큰 것 같다.
그럼 이제 어떻게 풀어야 O(N^2)보다 빠르게 풀 수 있을까?
해답은 누적 합
우리는 꿀벌이 지나가는 길을 직선적으로 더해나갔다.
어차피 더하기만 할거라면, 굳이 매번 for문으로 더해보아야 할까?
겹치는 구간을 매번 왔다갔다 하는 격인데, 굳이 그래야 할까?
반복되는 구간을 미리 계산 해놓고 간단한 연산만 하도록 한다면?
누적 합 개념을 이용하여 한 번 결과를 저장해놓고 이용해보자
cin >> num;
cin >> fields[0];
pile_sum[0] = fields[0];
for (int i = 1; i < num; i++) {
cin >> fields[i];
pile_sum[i] = pile_sum[i - 1] + fields[i];
}
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀벌 - 꿀통 - 꿀벌
sum = (pile_sum[i] - pile_sum[0]) + (pile_sum[num - 2] - pile_sum[i - 1]);
// 꿀벌 1 + 꿀벌 2
answer = max(answer, sum);
}
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀벌 - 꿀벌 - 꿀통
sum = (pile_sum[num - 1] - pile_sum[0] - fields[i]) + (pile_sum[num - 1] - pile_sum[i]);
answer = max(answer, sum);
}
for (int i = 1; i < num - 1; i++) {
int sum = 0;
// 꿀통 - 꿀벌 - 꿀벌
sum = (pile_sum[num - 2] - fields[i]) + pile_sum[i - 1];
answer = max(answer, sum);
}드디어 문제가 풀렸다!
해답은 누적 합을 이용해서, 시간을 최소화 하는 것이었다.
이렇게 되면, 동일 구간을 반복해서 계산할 필요가 없다.
어려운 알고리즘 문제는 하나의 개념만 이용하지 않는다.
보다 다양한 개념을 조합하여 문제를 풀 수 있어야 한다.
좀 더 창의적이고 넓은 시각으로 문제를 바라보자.