[백준 / BOJ] 1074번 Z ( Javascript / Node js )

 

1074번: Z

N이 3일 때

 

 

문제 풀이

 

얼핏 봤을 떄 분할과 정복을 사용하는 문제로 보이지만 아직 분할과 정복에 조예가 깊지 않았고,

그렇다고 풀이를 보기는 싫어서 다른 해법을 찾기 위해 우선 최대한 그림에서 규칙을 발견해보려 했다.

 

규칙을 찾아 수열식을 세우기만 한다면 재귀함수를 사용하여 해결할 수 있을 것 같다고 생각했기 때문이다.

 

그리고 좌표 ( 2 * x , 2 * y ) 의 값은 ( x , y ) 의 값의 4배라는 것을 찾아냈다.

단적인 예로 ( 1, 1 ) = 3, ( 2, 2 ) = 12, ( 4, 4 ) = 48이며 ( 1 , 3 ) = 11, ( 2, 6 ) = 44 다.

즉 ( 1 , 1 ) 의 값이 3이란 것만 선언해두면 ( 4 , 4 ) 의 값을 좌표에 2를 곱하는 과정을 반복하여 48이란 값을 구할 수 있는 것이다.

 

이런 방식으로 1 ( 0, 1 ) , 2 ( 1 , 0 ) , 3 ( 1 , 1 ) 좌표에서 시작하여 내가 찾고자 하는 값까지 도달하면 된다. 하지만 이걸론  아직 부족하다.

[ ( 0, 1 ) , ( 1 , 0 ) , ( 1 , 1 ) ] 이 세 좌표를 "근원 좌표"라 칭하겠다.

 

2로 나누다 보면 "근원 좌표"에 도달하기 전에 x 혹은 y 가 2로 나누어 떨어지지 않는 수 즉, 홀수가 되는 경우가 생길 것이기 때문이다. ex ) ( 6, 2 ) => ( 3 , 1 )

 

그렇다면 우리가 해야할 일은 x와 y중 홀수인 곳을 1을 빼주면 된다. 왜냐하면 반드시 x와 y좌표가 모두 짝수인 수를 시작으로 1, 2, 3을 더한 값들이 가장 작은 2 x 2 크기의 상자안을 채우기 때문이다.

ex) 8 ( 0 , 2 ), 9 ( 0 + 1, 2 ), 10 ( 0 , 2 + 1 ), 11 ( 0 + 1 , 2 + 1)

 

여기서 한가지 더 알아낼 수 있는 것은 2 x 2 박스안에서 x좌표가 1증가하면 값이 1 증가하고, y좌표가 1증가하면 값이 2가 증가한다는 것이다.

 

이를 이용해서 11은 ( 1 , 3 ) 으로 x, y 모두 홀수이니 x와 y 좌표를 모두 1씩 감소시킨 다음 3 (1 + 2)을 빼준 8로 이동하면 된다.

 

위 개념들을 이용하면 아래와 같이 재귀함수를 이용해 간단히 문제를 해결할 수 있다.

전체코드

 

const fs = require("fs");

const [N, r, c] = fs

  .readFileSync("../input.txt")

  .toString()

  .trim()

  .split(" ")

  .map((item) => Number(item));

const func = (N, r, c) => {

  if (N === 0) {

    return 0;

  }

  return (

    2 * (r % 2) + (c % 2) + 4 * func(N - 1, Math.floor(r / 2), Math.floor(c / 2))

  );

};

console.log(func(N, r, c));