[백준] 2477. 참외밭 (C++)

Key

- 밭 영역의 넓이를 어떻게 구할 것인지 고민해야한다.

- 입력받는 수들의 범위가 작기 때문에 시간복잡도나 배열 메모리를 신경써야하는 문제는 아니다.

 

Idea

1. 밭 영역을 여러 사각형으로 잘라서 더하는 방법도 있지만 전체 넓이에서 파란영역을 빼는게 훨씬 쉬울거라 생각했다.

2. 이제 파란 영역을 어떻게 구할지가 문제인데, 처음엔 방향이 꺾일 때마다 가로 * 세로로 넓이를 구한 후 어떻게든 규칙을 찾아보려고 했다. 그런데 아래 그림처럼 출발 지점에 따라 값이 완전히 바뀌는 문제가 있었다.

 

 

3. 방향에서 규칙을 찾았다. 두번씩 입력되는 방향 중에 반복되는 특정 방향 사이에 껴있는 방향을 구해야한다.

 

예를 들어, 예시에서는 방향이 4 2 3 1 3 1 순으로 입력된다. 여기서 3, 1이 두번 나오는 방향이고 3 사이에 껴있는 1(60)과 1 사이에 껴있는 3(20)이 파란 영역의 가로, 세로 길이가 된다.

 

한번씩 입력되는 방향은 육각형의 가장 큰 가로, 세로이다.

따라서 최종 식은 (한번 입력되는 방향1 * 한번 입력되는 방향2) - (반복되는 방향 사이에 껴있는 두번 나오는 방향1 * 반복되는 방향 사이에 껴있는 두번 나오는 방향2) 가 된다.

 

이 때 주의할 점은, 시작점이 정해져있는게 아니기 때문에 1 4 2 3 1 3 이나 3 1 4 2 3 1 처럼 입력될 수 있다. 그러면 0번 인덱스와 4번 인덱스 혹은 1번 인덱스와 5번 인덱스를 비교해야하는 상황이 생긴다. 따라서 모듈러 연산으로 i+2번째까지 비교를 해줘야한다.

 

현재 위치(i)와 다다음 위치(i+2)가 같고, 사이에 껴있는 수(i+1)가 두번 입력된 방향이라면 파란 영역의 변이다.

 

Code

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

int main() {
	int K;
	int arr[6][2] = { 0, };
	int cnt[5] = { 0, };
	int bSquare = 1;
	int sSquare = 1;

	cin >> K;

	for (int i = 0; i < 6; i++) {
		// 방향, 길이
		cin >> arr[i][0] >> arr[i][1];
		cnt[arr[i][0]]++;
	}

	for (int i = 0; i < 6; i++) {
		if (cnt[arr[i][0]] == 1) {
			bSquare *= arr[i][1];
		}

		if (arr[i][0] == arr[(i + 2) % 6][0]) {
			sSquare *= arr[(i + 1) % 6][1];
		}
	}

	cout << K * (bSquare - sSquare) << "\n";

	return 0;
}