[JS] 백준 2630번 색종이 만들기

---

문제 링크

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

풀이 전략

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

코드 

const fs = require("fs");
const input = fs
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((v) => v.split(" ").map(Number));

const n = input.shift()[0];

solution(input);

function solution(arr) {
    let white = 0;
    let blue = 0;

    recursive(0, 0, n);

    function recursive(x, y, size) {
        let cnt = 0;
        for (let i = 0; i < size; i++) {
            for (let j = 0; j < size; j++) {
                cnt += arr[x + i][y + j];
            }
        }

        if (cnt === 0) white++;
        else if (cnt === size * size) blue++;
        else {
            size /= 2;
            recursive(x, y, size);
            recursive(x + size, y, size);
            recursive(x, y + size, size);
            recursive(x + size, y + size, size);
        }
    }

    console.log(white);
    console.log(blue);
}

 

회고

N도 최대가 될 수 있는 수가128이고 이정도 연산은 컴퓨터가 충분히 해낼 수 있으니 모두 검사하는 브루트포스를 떠올릴 수 있었다. 그리고 만약 n 이 8이면 이것을 점점 나누어 4, 2, 1로 줄어들기 때문에 재귀로 나누어 주면 된다고 생각하였다. 이때 흰색인지 파란색인지 판별하는 코드가 필요하였는데, 파랑색이 1로 되어있기 때문에 n * n을한 값과 같다면 그 칸은 모두 파란색이라 판단할 수 있었다. 그리고 어떤 범위가 white와 blue면 종료하고 아니면 재귀적으로 호출하여 들어간다. 분할정복의 개념을 알 수 있는 문제였다. 

 

더 좋은 방법이나 의견이 있으시다면 댓글 부탁드립니다 :)