[BOJ] 2477번_참외밭_구현 (C++)

[문제]

https://www.acmicpc.net/problem/2477

참외밭에서 참외의 개수를 세려고 한다. 1m^2의 넓이에 자라는 참외 개수를 알고 있을 때 참외밭의 참외 개수를 구하는 문제이다. 조건은 다음과 같다.

1. 참외밭의 모양은 ┌,┐,┘,└ 모양인 육각형이다.
2. 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다.

[사용 알고리즘]

구현

[풀이 핵심]

• 참외밭은 큰 직사각형에서 작은 직사각형을 뺀 육각형 모양인 점을 이용하면 해결할 수 있다.
• 큰 직사각형의 넓이는 너비와 높이의 최대값을 구해서 곱해주면 간단하게 구할 수 있다.
• 작은 직사각형의 넓이를 구하는 것이 이 문제의 핵심인데, 문제의 두번째 조건인 '참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다.'을 이용하면 해결할 수 있다. 구하는 방법은 다음과 같다. 너비, 높이의 최대값이 나온 index에서 반시계방향으로 3칸 이동하면 최소 너비와 높이를 구할 수 있다. 이를 곱해주면 작은 직사각형의 넓이를 구할 수 있다.
• 마지막으로 큰 직사각형의 넓이와 작은 직사각형의 넓이를 빼서 참외밭의 넓이를 구해주고, K(1m^2당 참외 개수)를 곱해주면 답이다.

[코드]

//boj2477번_참외밭_구현

#include<iostream>
#include<vector>

using namespace std;

int main() {
	int K;
	cin >> K;

	vector<pair<int, int>> v;

	for (int i = 0; i < 6; i++) {
		int dir;
		int leng;

		cin >> dir >> leng;

		v.push_back({ dir,leng });
	}

	int maxWidth = 0;
	int maxHeight = 0;

	int maxWidth_index = 0;
	int maxHeight_index = 0;

	for (int i = 0; i < 6; i++) {
		if (v[i].first == 1 || v[i].first == 2) {
			if (v[i].second > maxWidth) {
				maxWidth = v[i].second;
				maxWidth_index = i;
			}

		}
		else if (v[i].first == 3 || v[i].first == 4) {
			if (v[i].second > maxHeight) {
				maxHeight = v[i].second;
				maxHeight_index = i;
			}
		}
	}
	int minWidth = v[(maxWidth_index + 3) % 6].second;
	int minHeight = v[(maxHeight_index + 3) % 6].second;

	cout << ((maxWidth * maxHeight) - (minWidth * minHeight)) * K;

	return 0;
}