[JS] 백준 2563 색종이

 

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

2563번: 색종이

 

 

 

색종이

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

20346

14068

11961

69.866%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

3
3 7
15 7
5 2

예제 출력 1 복사

260

 

 

 

 

---

- 문제 접근

처음에는 주어진 사각형의 넓이를 모두 구하고 겹치는 부분에 대해 빼주려고 했다.

그래서 겹치는 부분을 찾기 위해 주어진 여러 사각형 시작 좌표들의 x값과 y값을 각각 비교해, 각 좌표들의 x값과 y값 차이의 절대값이 10보다 작으면 겹치는 부분이 있으므로

겹치는 부분의 넓이를 (|a의 x좌표 - b의 x좌표|+10) * (|a의 y좌표 - a의 y좌표|+10) 로 구하려했다.

그러나 모든 주어진 예제입력의 시작좌표들을 일일히 하나하나 다 비교하기 어려울 것 같았고, 한번 이상 중복되는 부분의 너비를 빼주기도 어려울 것 같아 다른 방법이 있을 것이라 생각했다.

 

그래서 검색해보니, 100*100의 2차원 배열을 미리 만들어두고, 그 배열 내부를 채우는 방식으로 하면 쉽게 할 수 있다는 것을 알았다.

너비 자체를 구하는 것이 아니라 한칸한칸을 따지므로 continue로 간단하게 겹쳐진 부분을 제외하고 너비를 잴 수 있었다.

 

- 풀이

let [TC, ...input] = require("fs")
  .readFileSync("dev/stdin")
  .toString()
  .split("\n");
input = input.map((i) => i.split(" "));
const arr = Array.from(Array(100), () => Array(100).fill(0));
let count = 0;

for (let i = 0; i < TC; i++) {
  let startX = +input[i][0]; // 3
  let startY = +input[i][1]; // 7
  for (let l = 0; l < 10; l++) {
    for (let m = 0; m < 10; m++) {
      if (arr[startX + l][startY + m] !== 0) {
        continue;
      }
      if (arr[startX + l][startY + m] === 0) {
        arr[startX + l][startY + m] = 1;
        count++;
      }
    }
  }
}
console.log(count);