백준_2563 <색종이>

2563번: 색종이 (acmicpc.net)

2563번: 색종이

좌표평면을 다루는다는 생각으로 접근했다. X좌표의  MAX = 100, Y좌표의  MAX= 100. 100X100 짜리 좌표평면에 

10X10짜리 정사각형 N개를 올리고, 이 N개들의 넓이의 영역을 구하는 문제이다.

10X10짜리 정사각형이 3개있고 이들이 자신들의 영역이 아닌 각자의 영역을 서로 침범할 경우 넓이의 영역이 300보다 작아지겠다. 이를 고려해야하는 문제임.

 

내 첫번째 접근은 패턴을 찾는 것이었다. input이 예를들어 3 7 / 15 7 / 5 2면 3 7와  15 7은 서로 영역 침범을 하지 않겠다.

하지만 3 7 / 5 2는 영역을 침범을 하겠다. 

아래와 같은 경우이다. 이럴 때는 겹친 넓이를 한번 빼줘야하겠다.

따라서 input된 xy좌표들로 패턴을 만들어 바로 넓이를 구해볼까 했다가. 위와 같은 경우가 아닌 n이 커진다면 매우매우 복잡해지기에 그런 구현을 포기했다.

 

두번째 접근은 바로 100x100짜리 2중 배열을 만드는 것이다. 그리고 input된 xy좌표로 10x10짜리 정사각형모양을 구성하는 xy좌표에 값을 할당했다, 2중배열은 int type으로 만들었고 input된 xy좌표를 훑고 지나간다면 값을 올려준다.

이렇게 되면 겹치는 부분도 아주 깔끔하게 해결할수있겠다. 훑고 지나갈때 값이 2이상이라면 이 부분은 2번 이상 겹쳤기에 값을 빼줘야겠다 !

주의해야할점은 만약 3번 겹치면 값을 2빼야지 순수하게 겹치는 넓이들을 구하기에 이를 주의하고 코드를 짜면 끝.

글로는 설명이 부족하다. 아래 코드를 참고하면 좋겠다.

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int 색종이 = sc.nextInt();
		int 겹친부분 = 0;
		int 붙인넓이 = 색종이*100;
		int[][] arr = new int[100][100];
		for(int i=0; i<색종이; i++) {
			int 왼쪽변 = sc.nextInt();
			int 아랫쪽변 = sc.nextInt();
			for(int j=왼쪽변; j<왼쪽변+10; j++) {
				for(int k=아랫쪽변; k<아랫쪽변+10; k++) {
					arr[j][k] =arr[j][k]+1;
				}
			}
		}
		
		for(int i=0; i<100; i++) {
			for(int j=0; j<100; j++) {
				if(arr[i][j] >=2) {
					겹친부분 += (arr[i][j]-1);
				}
			}
			
		}
		System.out.println(붙인넓이-겹친부분);
		
	}

}