[c++/백준] 2477번: 참외밭

문제 링크

2477번: 참외밭

풀이

먼저 밭이 육각형인 것만 생각하면 된다. 특징은 제일 큰 사각형에서 작은 사각형을 빼면 된다는 것.
또한, 입력 받을 때 가로 세로가 번갈아서 입력 받는다는 점.

1. 밭 크기를 입력 받으며 arr를 초기화한다.
2. 큰 사각형의 너비와 높이를 구할건데, arr의 홀수 인덱스와 짝수 인덱스는 각각 너비와 높이, 혹은 높이와 너비가 될 것이다. 그렇게 max1과 max2를 갱신하고, 각각의 인덱스도 갱신한다.
3. 2번 과정을 통해 maxFlag는 제일 큰 너비와 높이에 1로 초기화가 되어있을텐데, 그림의 빨간펜과 같다.
   
   3-1. 특징을 생각해보면, 작은 사각형은 양 옆에 max1과 max2 값이 없는 걸 알 수 있다.
   그림의 160과 50 값은 자기 자신이 제일 큰 값이니 고려할 필요 없고, 30과 100은 양 옆에 maxFlag==1인 값이 있고, 60과 20은 없다. 즉 60과 20은 작은 사각형이 되게 된다.
   3-2. 그래서 minus에 작은 사각형 넓이를 구해주고 (max1*max2(큰 사각형 넓이) - minus(작은 사각형 넓이)) * k(참외가 나는 개수)를 출력하면 된다.

코드

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

int main(void)
{
	int k;
	cin >> k;
	
	vector<int> arr(6);
	vector<bool> maxFlag(6);
	for (int i = 0; i < 6; i++)
	{
		int tmp;
		cin >> tmp>> arr[i];
	}

	int max1 = 0, max2 = 0; // 제일 큰 너비, 높이 구하기
	int idx1, idx2;
	for (int i = 0; i < 6; i++)
	{
		if (i % 2 == 0)
		{
			if (max1 < arr[i])
			{
				max1 = arr[i];
				idx1 = i;
			}
		}
		else
		{
			if (max2 < arr[i])
			{
				max2 = arr[i];
				idx2 = i;
			}
		}
	}

	maxFlag[idx1] = 1;
	maxFlag[idx2] = 1;

	int minus = 1;

	for (int i = 0; i < 6; i++)
	{
		if (maxFlag[i] == 1) continue;
		if (i == 0)
		{
			if ((maxFlag[i + 1] | maxFlag[5]) == 0) minus *= arr[i];
		}
		else if (i == 5)
		{
			if ((maxFlag[0] | maxFlag[i - 1]) == 0) minus *= arr[i];
		}
		else
		{
			if ((maxFlag[i - 1] | maxFlag[i + 1]) == 0) minus *= arr[i];
		}
	}
	

	cout << (max1 * max2 - minus)*k << endl;

}