[백준] 1072번 Z _ Node_js

문제

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

1074번: Z

---

문제 풀이

 해당 문제는 규칙을 찾아 해당 규칙을 통해 답을 구하는 수학 문제이다. 

 

숫자의 진행 방향은 Z모양으로 2^n X 2^n 단위로 진행이 된다. 그렇기에 여기서 규칙을 찾을 수 있다.

 

아래 그림을 보자.

 

Z모양의 크기는 2^2k만큼 증가하는데 이를 x축과 y축 별로 증가하는지 작성해보았다. 각 x축은 2^2x, y축은 2^(1+2y)만큼 씩 증가한다. 그렇기에 시작점을 수학적으로 옮기며 해당 위치의 순서를 알 수 있다. 식과 그림만으로는 이해가 힘든 것 같다.

 

아래 코드를 보면서 좀 더 자세하게 풀어보자

while(y >= 2 || x >= 2){
    // console.log('(x,y) : ',x,y)
    xscale = 0;
    yscale = 0;
    while(Math.pow(2,xscale + 1) <= x)   xscale++;
    while(Math.pow(2,yscale + 1) <= y)   yscale++;
    
    // console.log('xscale :',xscale,'yscale :',yscale);
    if(yscale > 0){
        answer += Math.pow(2,1+(2*yscale));
        // console.log(answer);
        y -= Math.pow(2,yscale);
    }
    if(xscale > 0){
        answer += Math.pow(2,(2*xscale));
        // console.log(answer);

        x -= Math.pow(2,xscale);
    }
    // console.log('After (x,y) : ',x,y)
}

우선 Z모양의 최소 크기인 2x2 상자가 만들어질 때까지 상자를 작게만드는 과정을 진행해야한다.

x와y 크기를 2의 제곱으로 구한다. 이렇게 된다면 큰 제곱수부터 제거 될 것이다.

 

10 6 4 입력을 예로 해여 코드를 실행하면 아래와 같은 결과가 나온다.

(x,y) :  4 6
xscale : 2 yscale : 2
32
48
After (x,y) :  0 2
(x,y) :  0 2
xscale : 0 yscale : 1
56
After (x,y) :  0 0

각 2의 거듭곱수만큼 좌표를 줄이고, 그에 맞는 answer 값을 증가시키며 시작 지점을 옮겨준다. 이를 x,y크기가 2 미만이 될 때 까지 진행한다.

 

이 후 해당 위치 별 값을 저장한 twoXtwoCase를 통해 값을 추출한다.

const twoXtwoCase = {
    '00' : 0,
    '10' : 1,
    '01' : 2,
    '11' : 3
}

console.log(answer+ twoXtwoCase[[x,y].join('')]);

 

수학 문제들은 필자의 글솜씨로 설명을 잘 못하는 것과 더해 직접 풀어보지 않으면 이해가 힘들기 때문에 직접 노트에 풀어보는 것을 추천한다. 

 

10분간 저렇게 규칙을 찾았다....ㅜ

 

---

제출 코드

const fs = require('fs');
const stdin = (process.platform === 'linux'? fs.readFileSync('/dev/stdin').toString() :
`10 6 4`).split('\n');

const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();


let [N,y,x] = input().split(' ').map(Number);
let answer = 0;
const twoXtwoCase = {
    '00' : 0,
    '10' : 1,
    '01' : 2,
    '11' : 3
}

let xscale = 0;
let yscale = 0;

while(y >= 2 || x >= 2){
    xscale = 0;
    yscale = 0;
    while(Math.pow(2,xscale + 1) <= x)   xscale++;
    while(Math.pow(2,yscale + 1) <= y)   yscale++;
    
    if(yscale > 0){
        answer += Math.pow(2,1+(2*yscale));
        y -= Math.pow(2,yscale);
    }
    if(xscale > 0){
        answer += Math.pow(2,(2*xscale));

        x -= Math.pow(2,xscale);
    }
}
console.log(answer+ twoXtwoCase[[x,y].join('')]);