[BOJ 25210] 백준 25210번 - 정사각형 세기

		2022 인하대학교 프로그래밍 경진대회(IUPC) 풀이
A		[BOJ 25205] 경로당펑크 2077
B		[BOJ 25206] 너의 평점은
D		[BOJ 25208] 새벽의 탐정 게임
E		[BOJ 25209] 샤카샤카
F		[BOJ 25210] 정사각형 세기
G		[BOJ 25212] 조각 케이크
H		[BOJ 25214] 크림 파스타
I		[BOJ 25215] 타이핑

1. 문제

$25210$. 정사각형 세기 (2022 인하대학교 프로그래밍 경진대회(IUPC) F번)

백준 25210번 - 정사각형 세기 (https://www.acmicpc.net/problem/25210)

2. 풀이

1. 원점에 가까운 좌표 네 개로 minLx, minRx, minUy, minDy를 구한다.
2. 원점에 먼 좌표 네 개로 maxLx, maxRx, maxUy, maxDy를 구한다.
3. 위의 여덟 좌표를 이용하여 만들 수 있는 최소 크기 정사각형의 한 변의 길이 minlen, 만들 수 있는 최대 크기 정사각형의 한 변의 길이 maxlen을 구한다.

1. 특정 len 크기의 정사각형이 왼쪽(left)에서 움직일 수 있는 범위를 구하고, 그 길이를 알아낸다. 마찬가지로 right, up, down에 대해서도 수행한다.
2. max(0, min(left, right)) * max(0, min(up, down)) 값을 계산하여 현재 len의 정사각형이 가능한 개수를 구한다.
3. minlen과 maxlen 사이의 모든 각각의 len에 대해 아래 작업을 수행하며 누적합을 구한다.

3. 채점 결과

4. 회고

생각이 정리되기까지 꽤 많은 시간이 걸렸다. 그림으로는 부족해서 직접 파워포인트에서 사각형을 움직여가며 범위를 생각했다.

maximum 값을 0으로 설정하지 않아 음수 값이 도출되어 WA를 받았다.

5. 코드