[백준] 2563번: 색종이 -JS

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

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

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

예제 입력1

3
3 7
15 7
5 2

예제 출력1

260

 

실버에 들어서기 시작한게 확 느껴지는 문제였다...ㅜㅜ 문제 읽고 도저히 감이 안잡혀서 그림도 그려보고 식도 써보고 한 결과...

"100*색종이 수 - 겹치는 영역= 색종이 넓이 " 를 생각했다. 근데 문제는 겹치는 영역을 과연 어떻게 찾아야 하는가였다.

내가 생각한 방법으로 하면 뭔가 너무 복잡해질거 같아서 다른 분들은 어떻게 풀었나 참고해봤다.

 

참고 후에 알게된 좋은 방법이 합집합을 이용하는 것이었다. 합집합은 A={1,2,3}, B={3,4,5} 일때 A∪B={1,2,4,5}가 된다. 즉, 겹치는 것은 하나만 표시된다! 

=> 좌표별로 색종이의 넓이를 1씩 늘려가면서 좌표 위를 칠해가는데, 이미 칠해진 좌표는 칠하지 않고 다음 좌표로 넘어가면 결과적으로 생겹치는 부분이 제외된 색종이의 넓이가 구해진다.

 

let fs=require('fs');
let input=fs.readFileSync('/dev/stdin').toString().split('\n');
let num=Number(input[0])
let size=0;
let paper=Array.from(Array(100),()=>Array(100).fill(0));

for(let i=0; i<num;i++){
    let [x,y]=input[i+1].split(' ').map((n)=>Number(n));
    for(let i=x;i<x+10;i++){
        for(j=y;j<y+10;j++){
            if(paper[i][j]===1){
                continue;
            }
            paper[i][j]=1;
            size++;
        }
    }
}
console.log(size);

 

참고:

https://devcorner.tistory.com/entry/%EB%B0%B1%EC%A4%80-2563%EB%B2%88-%EC%83%89%EC%A2%85%EC%9D%B4