[백준 1074번] Z - python

문제 링크

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

1074번: Z

풀이

- 분할 정복 문제인 줄 알고 재귀로 풀었는데 몇번째로 방문하는지 순서를 계산하는데에서 막혀 다른 블로그에서 아이디어를 얻고 풀었다.

- 사분면을 기준으로 좌표와 좌표에 해당하는 값을 수정해주면 되었다. 

- 좌표 r, c는 

제 2사분면에 위치하는 경우 : 수정 x 

제 1사분면에 위치하는 경우 : c에서 size만큼 빼준 위치로 이동 

제 3사분면에 위치하는 경우 : r에서 size만큼 빼준 위치로 이동

제 4사분면에 위치하는 경우 : r와 c에서 size만큼 빼준 위치로 이동 

- 제2사분면 -> 제 1사분면 -> 제 3사분면 -> 제 4사분면 순으로 탐색하기 때문에 

좌표를 몇번째로 방문하는지 좌표에 해당하는 값을 저장하는 cnt 는 

제 2사분면의 경우 : 수정 x 

제 1사분면의 경우 : 제 2사분면을 탐색 후 탐색하므로 cnt += size*size

제 3사분면의 경우 : 제 2사분면과 제 1사분면을 탐색 후 탐색하므로 cnt += size*size*2

제 4사분면의 경우 : 제 2사분면과 제 1사분면, 제 3사분면을 탐색 후 탐색하므로 cnt += size*size*3

- 마지막에 n이 1이 되면 총 4칸을 가지고 있는 정사각형이 된다. 따라서 

r과 c가 모두 0 일 경우 : 제 2사분면에 위치하므로 그대로 cnt 출력 

r이 0, c가 1 일 경우 : 제 1사분면에 위치하므로 cnt+ 1 출력 

r이 1, c가 0 일 경우 : 제 3사분면에 위치하므로 cnt+2 출력 

r과 c가 모두 1 일 경우 : 제 4사분면에 위치하므로 cnt+3 출력 

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

# 좌표를 몇 번째로 방문하는지 좌표에 해당하는 값 
cnt = 0

# n이 1이면 멈춤 
while n > 1:
  size = (2**n)//2
  # 제 2사분면 : 좌표 수정 x 
  if r < size and c < size:
    pass 
  # 제 1 사분면 : c 좌표 수정
  elif r < size and c >= size:
    cnt += size*size 
    c -= size 
  # 제 3 사분면 : r 좌표 수정 
  elif r >= size and c < size:
    cnt += size*size * 2. 
    r -= size 
  # 제 4사분면 : r,c 좌표 수정 
  elif r >= size and c >= size:
    cnt += size*size *3
    c -= size
    r -= size 
  n -= 1 

cnt = int(cnt)
# 제 2사분면 
if r == 0 and c == 0:
  print(cnt)
# 제 1사분면 
if r == 0 and c == 1 :
  print(cnt + 1)
# 제 3사분면 
if r == 1 and c == 0:
  print(cnt + 2)
# 제 4사분면 
if r == 1 and c== 1:
  print(cnt +3)