백준 2571 색종이-3

작성일 | In |

Problem : 색종이-3

유형 : 구현

문제 설명

그림

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다. 첫째 줄에 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 출력한다.

예제 입력

1
2
3
4
3
3 7
15 7
5 2

예제 출력

1
120

해결 전략

색종이를 먼저 붙인뒤, 색종이인 부분을 찾는다.
우측이 색종이가 아닌곳까지 탐색한다. (가로 길이)

색종이 였던 좌표에서 최대한 아래로 내려가본다.
만약 시작 좌표를 포함하고 우측으로 두칸 갈 수 있었고 (가로 길이 2)
첫번째 칸에서 최대 3칸을 내려갈 수 있었으며,
두번째 칸에서 최대 4칸을 내려갈 수 있었다면
아래로 동일하게 내려 갈 수 있는 최대 길이는 3이 된다. (세로 길이 3)

즉 얼마나 동일하게 아래로 갈 수 있는지를 구하면 된다.
해당 직사각형의 넒이는 2 x 3 = 6 이 된다.

주의할 점

  • 최소 값은 100이 될것이다.
  • 왜냐하면 직사각형의 모양이 안나와도 색종이 하나의 넓이는 항상 100이기 때문이다.

풀이

색종이를 세팅한다.

도화지의 방향이 달라도, 색종이만 정확하게 붙이면 된다.

색종이가 있는 좌표를 찾고, 해당 좌표에서 여러 직사각형을 그려본다.

  • 우측으로 갈 수 없을때까지 탐색한다.
  • area_check로 넘기는것은 해당 좌표, 우측으로 이동한정도(세로길이) 이다.

직사각형의 넓이를 계산한다.

  • 해당 좌표에서 최대한 아래로 내려가본다.
  • 만약 (3, 4, 3+1) 가 넘어 왔다면
  • (3,4) 좌표에서 우측으로 3번 갈 수 있다는 이야기이다. (가로 길이 총 4)
  • +1 인 이유는, 첫 좌표 때문에 한번 더해줘야한다.
  • (3,4), (3,5), (3,6), (3,7) 각각의 좌표에서 최대한 아래로 내려가본다(세로 길이)

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
#define MAX 101
using namespace std;

bool board[MAX][MAX];
int n;
int answer = 100;

int area_check(int nx, int ny, int dir) {
	int min_depth = 100;
	for (int ii = ny; ii < ny + dir; ++ii) {
		int depth = 0;
		for (int i = nx; i < 100; ++i) {
			if (!board[i][ii])break;
			depth++;
		}
		min_depth = min(min_depth, depth);
	}
	return min_depth * dir;
}

void solve() {
	for (int i = 0; i < 100; ++i) {
		for (int ii = 0; ii < 100; ++ii) {
			if (!board[i][ii])continue;
			for (int dir = 0; dir < 100; ++dir) {
				int ny = ii + dir;
				if (ny >= 100)break;
				int area = area_check(i, ii, dir+1);
				answer = max(answer, area);
			}
		}
	}
}

void board_set(int nx, int ny) {
	for (int i = nx; i < nx + 10; ++i) {
		for (int ii = ny; ii < ny + 10; ++ii) {
			if (board[i][ii])continue;
			board[i][ii] = true;
		}
	}
}

void input() {
	cin >> n;
	int nx, ny;
	while (n--) {
		cin >> ny >> nx;
		board_set(nx, ny);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

	input();
	solve();
	cout << answer;

	return 0;
}

피드백

복잡도를 더 개선한 풀이 방법이 존재한다.