[백준][C++] 21758 꿀 따기

21758. 꿀 따기

21758번: 꿀 따기

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

장장 2시간을 넘게 푼 문제... 처음 본 그리디 골드 문제에 기강을 세게 잡혔다...

풀어보니 생각보다는 어렵지 않았다는 게 화가 난다... 으엉엉

 

처음 접근은 양 끝 수를 비교해서 더 작은 쪽에 벌을 몰아놓고, 반대쪽에 꿀통을 넣을 생각이었다. 하지만, 이 접근은 반례가 너무 많았고... 신경쓸 조건들이 참 많았다.

 

양 끝 수만 비교해서 최적의 결과가 나오는 것도 아닐뿐더러, 두번째 벌의 위치를 정하는 것도 생각이 나지 않아서 머리가 뱅뱅 돌았다.

 

---

 

문제의 알고리즘 분류를 보고 힌트를 얻을 수 있었다. 그리디, 누적합, 많은 조건 분기가 있었는데... 사실 난 그리디를 제외하고 아무것도 몰랐다...

 

그래도 한국인이니 많은 조건 분기가 눈에 띄었다.

 

---

 

많은 조건에서 정답을 구하고, 그 중 가장 최적의 값을 답으로 쓰자고 생각했다.

생각한 조건은 3개이다.

 

1. 벌 꿀통 벌 (벌 사이에 꿀통이 있을 때)
2. 벌 벌 꿀통 (벌이 왼쪽에 몰려있고, 꿀통이 오른쪽에 있을 때)
3. 꿀통 벌 벌 (벌이 오른쪽에 몰려있고, 꿀통이 오른쪽에 있을 )

 

이 중 1번을 구하는 것은 매우 쉬웠다. 벌은 양 끝에, 꿀통은 유일하게 두 벌이 모두 지나갈수 있는 자리이므로 벌의 자리를 제외하고 가장 큰 값을 넣어주면 된다.

 

코드로 짜본다면

// 두 벌의 시작 자리 제외
answer = sum - arr[0] - arr[len - 1];

// max index
honey = max_element(arr.begin() + 1, arr.end() - 1) - arr.begin();
answer += arr[honey];

벌이 시작한 자리들을 제외하고, 꿀통은 두 벌이 모두 가므로 한 번 더 더해준다.

 

2~3번을 생각하는 건 시간이 조금 걸렸다.

간단하게 반복문을 돌려서 꿀 손해가 가장 적은 곳을 골랐다.

input =>
5 A B C D E

// 왼쪽 벌을 몰려있고, 오른쪽에 꿀통이 있을 때
// SUM = A + B + C + D + E

// A, B에 벌이 있다면
// EXCEPTION = -A-A-B-B

// A, C
// EXCEPTION = -A-C-A-B-C

// A, D
// EXCEPTION = -A-D-A-B-C-D

// A, N
// EXCEPTION = -2A-2N-(B~N-1)

Exception이 가장 적을 때의 두번째 벌의 자리를 지정했다.

 

int BeeBeeHoney(vector<int> v, int sum)
{
    int exception = -2147483647;

    for (int i = 1, honeySum = 0; i < v.size(); i++)
    {
        int minus = -(arr[0] * 2) - (arr[i] * 2) - honeySum;

        if (exception < minus)
            exception = minus;

        honeySum += arr[i];
    }

    return sum * 2 + exception;
}

 

오른쪽에서 벌이 오는 상황이면, 매개변수의 벡터를 리버스해주었다.

 

전체 코드

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> arr;
int BeeBeeHoney(vector<int> v, int sum);

int main()
{
	int len, honey, sum = 0;
	int answer = 0;
	cin >> len;
	arr.resize(len);

	for (int i = 0; i < len; i++)
	{
		cin >> arr[i];
		sum += arr[i];
	}

	// CASE 1
	// BEE HONEY BEE
	// µÎ ¹úÀÇ ½ÃÀÛ ÀÚ¸® Á¦¿Ü
	answer = sum - arr[0] - arr[len - 1];

	// max index
	honey = max_element(arr.begin() + 1, arr.end() - 1) - arr.begin();
	answer += arr[honey];

	// CASE 2
	// BEE BEE HONEY
	int temp = BeeBeeHoney(arr, sum);

	if (temp > answer)
		answer = temp;

	// CASE 3
	// HONEY BEE BEE
	reverse(arr.begin(), arr.end());
	temp = BeeBeeHoney(arr, sum);

	if (temp > answer)
		answer = temp;

	cout << answer;
}

int BeeBeeHoney(vector<int> v, int sum)
{
	int exception = -2147483647;

	for (int i = 1, honeySum = 0; i < v.size(); i++)
	{
		int minus = -(arr[0] * 2) - (arr[i] * 2) - honeySum;

		if (exception < minus)
			exception = minus;

		honeySum += arr[i];
	}

	return sum * 2 + exception;
}

 

지금까지 푼 그리디 문제 중에 가장 어려웠다... 이제 슬슬 어려운 문제가 많이 나올 것 같다. 포기하지 말고 열심히 끝까지 풀어봐야지.

 

하나의 최적의 방법이 아니라, 여러가지 답을 산출할 수 있는 여러 조건을 생각하고 최적의 결과를 내는 법을 배웠다. 비슷한 문제가 나온다면, 시간을 날리지 않고 이 방법을 고려해봐야겠다.