[JavaScript] 백준 1074 : Z

level : silver 1
문제 링크 : Z

1074번: Z

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
const [N, r, c] = input.split(' ').map(Number);
let result = 0;
result = solution(0,2**N-1,0,2**N-1,r,c,result);
console.log(result);


function solution(row_start,row_end,col_start,col_end,r,c,num){
    const length = row_end-row_start+1;
    if(length===1)
        return num;
    const row_mid = (row_start+row_end)/2;
    const col_mid = (col_start+col_end)/2;
    const len = (length/2)**2;
    /// 제 1 사분면
    if(r<row_mid&&c<col_mid)
        return solution(row_start,Math.floor(row_mid),col_start,Math.floor(col_mid),r,c,num);
    /// 제 2 사분면
    else if(r<row_mid&&c>col_mid){
        num+=len;
        return solution(row_start,Math.floor(row_mid),Math.ceil(col_mid),col_end,r,c,num);
    }
    /// 제 3 사분면
    else if(r>row_mid&&c<col_mid){
        num+=2*len;
        return solution(Math.ceil(row_mid),row_end,col_start,Math.floor(col_mid),r,c,num);
    }
    /// 제 4 사분면
    else{
        num+=3*len;
        return solution(Math.ceil(row_mid),row_end,Math.ceil(col_mid),col_end,r,c,num);
    }
}

풀이방법

위의 그림과 같이 각각 k 사분면이라 칭하였다.(k는 1~4 사이의 임의의 자연수이고 고등학교에서 배운 평면 좌표계의 사분면과는 약간의 차이가 있습니다.)

처음 2^N x 2^N matrix에서 원하는 좌표를 찾을 때 까지 사분면을 기준으로 값을 찾는 recursion함수를 이용한다.
row와 col을 길이는 서로 같다.
길이를 기준으로 4개의 사분면으로 나눌 수 있고 각각의 사분면에 따라 각각 (길이)*(k-1)을 num에 더해주며 반복하면 된다.

느낀점
처음에는 위치에 따라 수학적으로 수식이 나올 것 같았지만 찾지 못하였다. 그리하여 재귀함수를 이용하여 풀이하였다.
규칙성을 단일 수식으로 바꾸어서 풀 수 있어야 한다는 관념을 버려야겠다.