[백준] 1074 - Z (Javascript / node)

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

1074번: Z

핵심 아이디어   

1. 분할정복으로 영역을 나누며 구해야 하는 행과 열에 근접해 간다.

2.재귀로 영역을 구하고 이때 구해야 하는 행과 열이 아닌경우 바로 정사각형 넓이만큼 카운터를 추가

구현 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
// N : 제곱정수, r : 행 c : 열
const [N, r ,c] = input[0].split(" ").map(Number);

let res = 0;
const divide = (row, col, size) => {
  if (row === r && col === c) {
    // 해당 좌표
    console.log(res);
    return;
  }
  if (r >= row && r < row + size && c >= col && c < col + size) {
    size = parseInt(size / 2);
    divide(row, col, size);  // 1사분면 탐색
    divide(row, col + size, size); // 2사분면 탐색
    divide(row + size, col, size); // 3사분면 탐색
    divide(row + size, col + size, size); // 4사분면 탐색
  } else res += size * size; // 영역 이외
};

divide(0, 0, Math.pow(2, N));

 

1. 재귀를 위한 divide 함수를 만든

2. 영역에 해당(r과 c 영역안)된다면 재귀로 탐색

3. divde 재귀 순서는 Z모양 순으로 구현

4. 영역 밖에 있다면 해당 영역의 크기만큼 res에 더한다