[2477] 참외밭

 

 

정말 시간 많이 쓰고 완성된 코드도 솔직히 맘에 안들지만..

맞았으니까~^^

 

항상 저렇게 직사각형이 패인 모양으로 완성이 된다

처음에는 2차원 배열로 풀어보려 했으나 처참히 실패

 

알고리즘에 규칙이 있지 않을까 하면서 여러번 그려보았다

그래서 규칙을 발견했다

색칠한 건 패인 직사각형의 가로, 세로 길이

 

나는 큰 직사각형에서 패인 부분의 직사각형의 넓이를 빼고 싶었다

큰 직사각형의 가로, 세로는 쉽게 구할 수 있었다

		if (inf[i].dir == 3 || inf[i].dir == 4) { // 남북 (세로)
			max_row = inf[i].len > max_row ? inf[i].len : max_row;
		}
		else { // 동서 (가로)
			max_col = inf[i].len > max_col ? inf[i].len : max_col;
		}

 

근데 이제 패인 직사각형 구하는게 정말 힘들었다

무작정 작은 가로세로를 구하면 안됨..

정확히 꺾여 들어가는 부분을 찾아서 패인 직사각형을 구해야했다

 

생긴 육각형은 저 4가지로 분류되는데,

남-서-남, 서-남-서로 꺾여 들어가거나,

북-서-북, 서-북-서로 꺾여 들어가거나,

남-동-남, 동-남-동으로 꺾여 들어가거나,

북-동-북, 동-북-동으로 꺾여 들어갔다

 

그래서 일단 구조체에 방향, 길이 정보를 담고 탐색을 시작했다

struct info {
	int dir;
	int len;
};

 

그리고 구조체를 탐색을 해야되는데,,

파란색 선까지는 탐색을 할 순 있는데

저 빨간색, 보라색을 어떻게 탐색하나 싶은거임?!?!?!!?

 

결국.. 노가다

저 2가지 케이스만 따로 탐색을 해주었다 ㅠㅠ 코드 개못생김

 

전체 코드는 아래에 있다

#include <iostream>
using namespace std;

int K;
int max_row = -1, max_col = -1; // 큰 직사각형 넓이
int min_row, min_col; // 작은 직사각형 넓이

struct info {
	int dir;
	int len;
};

info inf[6];

int Com[4][2][3] = {
	{{2,3,2}, {3,2,3}},
	{{4,2,4}, {2,4,2}},
	{{3,1,3}, {1,3,1}},
	{{1,4,1}, {4,1,4}}
};

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> K;

	for (int i = 0; i < 6; i++)
	{
		cin >> inf[i].dir >> inf[i].len;
		if (inf[i].dir == 3 || inf[i].dir == 4) { // 남북 (세로)
			max_row = inf[i].len > max_row ? inf[i].len : max_row;
		}
		else { // 동서 (가로)
			max_col = inf[i].len > max_col ? inf[i].len : max_col;
		}
	}

	for (int i = 0; i < 4; i++) // inf를 움직임
	{
		for (int j = 0; j < 4; j++) { // Com을 움직임
			if (inf[i].dir == Com[j][0][0] && inf[i + 1].dir == Com[j][0][1] && inf[i + 2].dir == Com[j][0][2]) {
				min_row = inf[i + 1].len;
				min_col = inf[i + 2].len;
			}
			else if (inf[i].dir == Com[j][1][0] && inf[i + 1].dir == Com[j][1][1] && inf[i + 2].dir == Com[j][1][2]) {
				min_row = inf[i].len;
				min_col = inf[i + 1].len;
			}
		}
	}
	for (int j = 0; j < 4; j++) {
		if (inf[4].dir == Com[j][0][0] && inf[5].dir == Com[j][0][1] && inf[0].dir == Com[j][0][2]) {
			min_row = inf[5].len;
			min_col = inf[0].len;
		}
		else if (inf[5].dir == Com[j][1][0] && inf[0].dir == Com[j][1][1] && inf[1].dir == Com[j][1][2]) {
			min_row = inf[5].len;
			min_col = inf[0].len;
		}
	}
	int area = (max_row * max_col) - (min_row * min_col);
	printf("%d", area * K);

}