[백준 1074번] Z - java

문제 설명

1.2^N x 2^N 크기 배열에 대해 배열의 N, x축 r, y축 c가 주어진다.

2. Z모양으로 0, 1, 2, 3 ... 이렇게 숫자가 하나씩 늘어나며 들어간다.

3. r,c위치에 존재하는 숫자를 구하면 된다.

풀이 과정

 1. 가장 전형적인 분할 정복 문제이다.

 2. r, c의 위치를 생각할 때에 전체 배열을 4가지 범위로 나누어 찾으면서 구해나간다.

ex

 

초록색으로 존재하는 위치의 값을 찾으려 한다고 생각해 보자

 

전체 크기를 기준으로 4개의 frame으로 나누어서 현재 frame은 4번째에 해당한다.

그렇다면 현재 위치 이전의 모든 frame에 해당하는 숫자들을 더한 숫자로부터 시작하면 된다.

파란영역 크기 전체 + 빨간영역 크기 전체 + 노란영역 크기 전체 -> 초록색 영역이 존재하는 하늘색 영역의 처음 숫자

그리고 다시 해당 frame으로 짤라서 나타내면 이런 도형이 나올 것이고 이는 다시

이렇게 될 것이다. 

이처럼 전체 도형을 4개 영역으로 짜르고, 해당하는 부분에 맞춰서 작게 맞춰나가면 된다.

 

 3. 왼쪽위 / 오른쪽위 / 왼쪽아래 / 오른쪽아래 이렇게 4가지 부분으로 나누면 각각 부분은

  - 그냥 짜르기

  - 파란영역을 정답에 더한 후 짜르기

  - 파란영역, 빨간영역을 정답에 더한 후 짜르기

  - 파란영역, 빨간영역, 노란영역을 정답에 더한 후 짜르기

이렇게 하나씩 구해가면 정답에 가깝게 나올 것이다.

 4. 그리고, frame의 크기가 1이 되면 즉, 1x1이 되면 해당 영역 자체가 정답 r,c의 위치가 되므로 이 때의 값이 정답이 될 것이다.

코드