[문제풀이 후기] 백준 #2563 - 색종이

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

 

문제를 접했을 때의 첫 접근 방식

1. 색종이의 넓이 100 이니까, (전체 색종이 수 * 100) 을 한 다음에 겹치는 부분을 빼면 되겠다.
2. 색종이의 사이즈는 10 이니까, (x좌표 + 10), (y좌표 + 10) 까지 배열로 만들어서 겹치는 부분을 찾으면 되겠다.

 

근데 어떻게 찾지...? 그리고 겹치는 부분이 여러 개면 어떻게 처리하지..?

 

그렇다. "겹치는 부분" 이라는 키워드에 꽂혀버린다면 이처럼 잘못된 접근방식을 가져 난항에 빠지게 된다.

 

 

올바른 접근 방식

그냥 전체 도화지에서 붙여진 부분만 계산하면 된다.

 

 

풀이 과정

1. 전체 도화지를 2차원 배열로 생성한다.
2. 각 좌표 (x, y) 부터 (x + 색종이 너비, y + 색종이 너비) 까지의 값을 변경한다.
3. 값이 변경된 부분을 계산한다.

 

 

기본 상위 코드

import { readFileSync } from "fs";

const input = readFileSync(0).toString().trim();	// 입력값

const backgroundSize = 100;	// 도화지 너비
const paperSize = 10;		// 색종이 너비

let areaSize = 0;		// 색종이가 붙여진 영역의 넓이

// 첫 줄(개수)을 제외한 값들 (= 좌표)
const [, ...points] = input.split("\n");

 

첫 번째 시도 (결과 : 성공)

// 도화지 좌표 배열 설정 (기본값 : 0)
const background = Array.from({ length: backgroundSize }, () =>
  Array.from({ length: backgroundSize }, () => 0)
);

points.forEach((point) => {
  const [x, y] = point.split(" ").map(Number);

  // 색종이가 차지하는 부분의 좌표값++
  for (let i = x; i < x + paperSize; i++) {
    for (let j = y; j < y + paperSize; j++) {
      background[i][j]++;
    }
  }
});

// 좌표가 차지하는 부분을 count
for (let i = 0; i < backgroundSize; i++) {
  for (let j = 0; j < backgroundSize; j++) {
    if (background[i][j] > 0) {
      areaSize++;
    }
  }
}

console.log(areaSize);

 

문제점

: 다른 사람의 채점 결과에 비해 메모리와 시간이 높게 나옴

  (메모리 : 10068KB / 시간 : 152 ms)

 

원인

: 단순히 붙였냐 / 아니냐 여부인데, 겹치는 부분에서는 불필요하게 좌표의 값이 ++ 되고 있음

=> 기본값을 0 에서 boolean 값 (false) 으로 수정

 

두 번째 시도 (결과 : 성공)

// 도화지 좌표 배열 설정 (기본값 : false)
const background = Array.from({ length: backgroundSize }, () =>
  Array.from({ length: backgroundSize }, () => false)
);

points.forEach((point) => {
  const [x, y] = point.split(" ").map(Number);

  // 색종이가 차지하는 부분의 좌표값을 true로 변경
  for (let i = x; i < x + paperSize; i++) {
    for (let j = y; j < y + paperSize; j++) {
      background[i][j] = true;
    }
  }
});

// 좌표가 차지하는 부분을 count
for (let i = 0; i < backgroundSize; i++) {
  for (let j = 0; j < backgroundSize; j++) {
    if (background[i][j]) {
      areaSize++;
    }
  }
}

console.log(areaSize);

 

효과

: 메모리 (10068 KB -> 9696 KB), 시간 (150 ms -> 92 ms)

 

 

후기

접근 방식.. 문제의 함정에 속지 않는 연습을 해야 겠다.
아직 한참 멀었다