백준 1030번 프렉탈 평면 (JavaScript)

1초마다 가로세로가 N배씩 커지고 가운데 K*K개는 검은색으로 칠해진다.

이를 0초일 때부터 차곡차곡 블럭을 붙이면서 만들게 되면, O(N^s) 만큼의 시간복잡도와 공간복잡도를 가지게 된다. N는 최대 8이고 s는 최대 10이다. (2^3)^10 = 2^30 = 10^9 인데, 0,1을 1byte로 저장한다면 1GB의 공간이 필요하게 된다. 그래서 전부다 계산하는 것은 비효율적이고 문제의 128MB메모리 제한에 걸리게 된다.

그래서 역으로 x,y 좌표의 프렉탈 평면의 값이 무엇일지를 계산한다. find함수 내에서 하는 것이 바로 그 일이다. 먼저 복사 되기 이전의 가로길이(beforeWidth)를 구하고, n과 k를 이용해 x,y가 검은색으로 칠해지는 범위에 있는 값인지 확인한다.

만약 범위 안이라면 1을 리턴하고, 아니라면 이전 사각형의 위에 있으므로 나머지 연산을 통해 이전 사각형 위에서의 위치를 구하고 다시 find함수를 call해준다. 

이를 반복하며 width가 1이 되었을 때는 s가 0인 상황이므로 1을 리턴해준다.

아래는 JavaScript로 구현한 코드이다.

/** @format */

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
    input.push(line);
}).on("close", function () {
    //console.log(input);
    solve();
    process.exit();
});

function find(x, y, n, k, width) {
    if (width == 1) {
        return 0;
    }
    let beforeWidth = Math.floor(width / n);
    let start = Math.floor((n - k) / 2 * beforeWidth);
    if (x >= start && x < width - start &&
        y >= start && y < width - start) {
        return 1;
    }
    return find(x % beforeWidth, y % beforeWidth, n, k, beforeWidth);
}
function solve() {

    let line = input.shift();
    let spt = line.split(" ").map(x => parseInt(x));
    let s = spt[0];
    let n = spt[1];
    let k = spt[2];
    let r1 = spt[3];
    let r2 = spt[4];
    let c1 = spt[5];
    let c2 = spt[6];

    let ans = [];
    let width = Math.pow(n, s);

    for (let x = r1; x <= r2; x++) {
        let row = [];
        for (let y = c1; y <= c2; y++) {
            row.push(find(x, y, n, k, width));
        }
        ans.push(row);
    }
    for (let i = 0; i < ans.length; i++) {
        console.log(ans[i].reduce((a, b) => a + "" + b));
    }
}