2563번_색종이_java

1.문제

2.접근방식

처음에는 각 사각형의 영역의 넓이를 더하고 사각형마다 겹치는 영역을 빼는 방식으로 생각을 하였다.

문제의 예시의 경우 각 사각형의 넓이는 100이므로 100 + 100 + 100 - (13-5) * (12-7) = 300 - 8 * 5 = 260 이 된다.

그런데 해당 방법의 경우 사각형들이 겹치는 영역을 구하기 위해서는 사각형이 100개일 경우 1번 사각형이 2~100번 사각형과 겹치는 부분을 확인해야 하고 2번 사각형이 3~100번 사각형과 겹치는 부분을 확인해야 하는 것처럼 계산을 너무 많이 해야 할것 같았다.

그래서 다른 방법을 생각했는데 흰색 도화지 영역을 넓이 1의 1칸짜리의 2차원 배열로 만들어서 입력된 사각형들로 색칠이 되는 영역을 배열에서 체크를 한 후 체크된 영역을 카운트 하는 방식으로 진행했다.

3.코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String args[]) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
			
			boolean[][] square = new boolean[101][101];
			int n = Integer.parseInt(reader.readLine());
			
			for(int i=0; i<n; i++) {
				String[] strArr = reader.readLine().split(" ");
				int a = Integer.parseInt(strArr[0]);
				int b = Integer.parseInt(strArr[1]);
				
				for(int j=a+1; j<=a+10; j++) {
					for(int k=b+1; k<=b+10; k++) {
						square[j][k] = true;
					}
				}
			}
			
			int cnt = 0;
			for(int i=0; i<=100; i++) {
				for(int j=0; j<=100; j++) {
					if(square[i][j]) {
						cnt++;
					}
				}
			}
			
			writer.append(String.valueOf(cnt));
			writer.flush();
			writer.close();
		} catch (Exception e) {
			
		}
	}
}