백준 1074번 : Z
난이도 : 실버 1
-문제 소개
한 변의 길이가 2^N인 사각형에서 Z 형태로 탐색을 하면서 원하는 행과 열이 몇 번째로 탐색되는지 알아보는 문제입니다.
하지만 완전탐색을 하면 시간이 너무 오래 걸려서 풀 수 없는 문제이므로 분할정복을 하며 풀어야하는 문제입니다. 재귀 개념을 사용해서 풀면 풀 수 있습니다.
-조건
- N의 크기는 1부터 15까지이다. (1<=N<=15)
- 주어지는 행과 열(r, c)는 0보다 크거나 같고 2^N보다 작다. (0 ≤ r, c < 2^N)
-코드
N, r, c = map(int, input().split())
answer = 0
while N != 0:
N -= 1
size = 2 ** N
# 1사분면
if r < size and c < size:
answer += (size) * (size) * 0
# 2사분면
elif r < size and c >= size:
answer += (size) * (size) * 1
c -= size
# 3사분면
elif r >= size and c < size:
answer += (size) * (size) * 2
r -= size
# 4사분면
else:
answer += (size) * (size) * 3
r -= size
c -= size
print(answer)-해설
while문을 통해 반복문을 돌려줍니다. 반복문의 첫 줄에는 N -= 1이 있습니다. 이는 사각형을 양 변을 반절로 나누어 전체 사각형을 1/4로 만들어주는 역할을 합니다. 그렇게 사각형이 1,2,3,4사분면으로 나뉘어집니다. 여기서 모든 사분면을 탐색하지 않고, r과 c의 값에 따라 분할 탐색을 해야합니다. 1사분면일 경우 모든 수의 원점이 되는 역할을 하기 때문에 answer에 아무런 수도 더해주지 않습니다. 2,3,4사분면의 숫자들은 1사분면의 숫자에 (n-1)사분면을 곱해준 숫자이기 때문에 answer에 그만큼 더해줍니다. 그리고 작은 사각형의 내부로 들어갈 준비를 하기 위해 r과 c를 사분면에 따라 size만큼 줄여줍니다. 그리고 N이 1이 될 때까지 작은 사각형을 탐색하고, 최종 answer값을 출력해줍니다.
