문제

---

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

코드

---

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		boolean[][] matrix = new boolean[100][100];
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int i = 0; i < 4; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());

			for (int j = sx; j < ex; j++) {
				for (int k = sy; k < ey; k++) {
					matrix[j][k] = true;
				}
			}
		}

		int result = 0;
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				if (matrix[i][j]) {
					result++;
				}
			}
		}

		System.out.println(result);
	}
}

문제 이해

---

• 문제 제목 그대로 이해하면 된다.
• 4개의 줄에 걸쳐서 왼쪽 최하단, 오른쪽 최상단의 꼭짓점이 주어진다.
• 이때 4개의 사각형이 차지하고 있는 면적의 합을 구하면 된다.

풀이 방법

---

• X와 Y는 100 미만이다. 따라서 100 X 100개 크기의 2차원 배열을 준비한 후에, 매입력마다 들어온 사각형의 영역만큼 표시하면 된다.
• 표시가 끝나고 나면 표시된 영역의 합을 구한다.

핵심 포인트

---

• 수학적으로 접근할 필요가 없다. 다른 풀이도 존재할 수는 있겠으나 입력의 최대 크기가 100이하이기 때문에 O(n^2)의 풀이로도 충분히 해결할 수 있다.

보완할 점 / 느낀 점

---

• 이전에 풀었던 색종이문제와 완전히 똑같은 알고리즘의 문제이다.
• 그떄 풀었을 때는 수학적으로 접근하다가 풀이를 떠올리지 못하고 풀이를 찾아본 후 허탈했었다.
• 푼지 꽤 됐었는데 아직 풀이방법이 기억에 남아서 다행이다.
• 어려운 문제는 아니지만, 이런 유형의 문제는 확실히 숙달하고 있어야겠다.

참고자료

---