[ 백준 - 1074 ] Z

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

1074번: Z

개인적으로 다시 풀어도 어렵게 풀었다....

분할 정복 문제는 익숙하지 않고... 규칙 찾는것도 오래 걸렸다.

---

[ 📌 풀이 ]

처음 풀 때는 완전 탐색처럼 풀었는데 시간 초과가 났었다.

이유는 2^15 * 2^15 이기 때문에 접근이 주어진 0.5초는...

• 초록 글씨는 2^8 * 2^8 사이즈 일 때 해당 사분면에 포함된 좌표 범위이다.

[ 4분면으로 나눴을 때 모습 ]

• 주어진 문제는 2^n 크기이기 때문에 최소 크기는 2 * 2 => 최소 크기까지 줄여야 한다.
• 4개의 사분면으로 나누어서 찾고자 하는 좌표가 어디에 속하는지 알아야 한다.

ex)
2^3 * 2^3 판에서 찾고자 하는 좌표 (r, c)가 11(3, 1) 인 경우

1사분면으로 이동 -> 2^2 * 2^2 사이즈로 축소
3사분면으로 이동 -> 2^1 * 2^1 사이즈로 축소

• 최소 크기가 되었을 때 나는 2중 반복문을 돌려서 해결 했지만 더 좋은 방법은 있을거 같다.

---

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.12.28(Thu)
# Spend Time: 1h 25m
# Runtime   : 40 ms
# Memory    : 31120 KB
# Algoritm  : Prime Number
"""

import sys
N, r, c = map(int, sys.stdin.readline().split())
cnt = -1

def search(x, y, n):
  global r, c, cnt

  next_n = n // 2
  quad_cnt = pow(next_n, 2)

  if n != 2:
    if x <= r < x + next_n and y <= c < y + next_n:
      search(x, y, next_n)
    elif x <= r < x + next_n and next_n <= c:
      cnt += quad_cnt
      search(x, y + next_n, next_n)
    elif next_n <= r and y <= c < y + next_n:
      cnt += quad_cnt * 2
      search(x + next_n, y, next_n)
    else:
      cnt += quad_cnt * 3
      search(x + next_n, y + next_n, next_n)
    return

  for i in range(x, x + 2):
    for j in range(y, y + 2):
      cnt += 1
      if i == r and j == c:
        print(cnt)
        sys.exit()

search(0, 0, pow(2, N))

 

---

[ 📌 결과 - Python  ]

[ Result - Python ]