[백준/자바] 1074 Z

출처

---

설명

기존에 맞았던 코드가 재채점 되면서 틀려서 다시 풀었다.

2^N X 2^N인 2차원 배열을 Z 모양으로 탐색한다.

size는 2^n -> 2^(n-1) -> ... -> 2^1 -> 1로 가면서 주어진 r행 c열을 찾게 된다.

0 영역의 왼쪽 위의 행을 x, 열을 y라 하면 각 영역의 특징은 다음과 같다.

 

0 영역 : x <= r < x+size/2 이면서 y <=  c < y+size/2

1 영역 : x <=  r < x+size/2 이면서 y+size/2 <=  c < y+size

2 영역 : x+size/2 <=  r < x+size 이면서 y <=  c < y+size/2

3 영역 : x+size/2 <=  r < x+size 이면서 y+size/2 <=  c < y+size

 

0 영역이라면 앞선 영역이 없으므로 아무 값도 더하지 않고 넘어간다.

1 영역 이라면 앞서 0 영역을 모두 지나쳐야 도달할 수 있기 때문에 0 영역의 개수인 (size/2)^2만큼을 결괏값에 더한다.

2 영역 이라면 0 영역과 1 영역을 모두 지나쳐야 도달할 수 있기 때문에 2개의 영역의 개수인 (size/2)^2 * 2만큼을 결괏값에 더한다.

3 영역 이라면 0 영역, 1 영역과 2 영역을 모두 지나쳐야 도달할 수 있기 때문에 3개의 영역의 개수인 (size/2)^2 * 3만큼을 결괏값에 더한다.

 

n = 3일 때, size는 8이 되고 4가지 영역은 다음과 같다.

예제 2번을 기준으로 설명하면 현재 영역에서 7행 7열은 3 영역에 속하게 된다.

그럼 다시 사이즈를 반으로 줄이고 3 영역의 왼쪽 위의 행을 x, 열을 y로 놓고 계산하게 된다.

 

3 7 7 일때,

3영역 (16 * 3) -> 3영역 (4 * 3) -> 3영역 (1 * 3) => 63이 나오게 된다.

코드