[Algorithm] 백준 1074 : Z

문제
https://www.acmicpc.net/problem/1074
풀이 https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/1074.%E2%80%85Z/Z.py

처음 문제 이미지를 보고 Z가 반복되는 형식이 재귀를 사용해야하나 생각을 했었다.
그림을 직접 그려서 값을 찾으려고 해보니 사분면을 이용해 풀 수도 있을 것 같다는 느낌이 들었다.

사분면을 이용해 문제를 풀기 위해 N = 3인 경우 6행 6열을 몇 번째로 방문하는 것인지 규칙을 찾아 보았다.

이 문제에서는 0행 0열부터 시작하며, 몇 번째로 방문하는 가에 대해서도 0번부터 시작하므로 이 점을 주의해야 했다.

<N = 3 r = 6 c = 6 / N = 3 r = 5 c = 5>

< 풀이 코드 >

N, r, c = map(int, input().split())

r += 1
c += 1

start1 = 0
end1 = 2 ** N
start2 = 0
end2 = 2 ** N
part = [] #몇 사분면인지 구하는 리스트 - 마지막 값은 2x2사이즈에 해당
while (end1 - start1)/2 >= 1:
  point1 = (start1 + end1)/2
  point2 = (start2 + end2)/2
  if point1 < r:
    if point2 < c:
      part.append(4)
      start1 = point1
      start2 = point2
    else:
      part.append(3)
      start1 = point1
      end2 = point2
  else:
    if point2 < c:
      part.append(2)
      end1 = point1
      start2 = point2
    else:
      part.append(1)
      end1 = point1
      end2 = point2

result = 0
exp = 2
count = 1
while len(part):
  if count == 1:
    result += part.pop()
    count += 1
  else:
    result += exp * exp *(part.pop() - 1)
    exp *= 2
print(result - 1)