•
문제
•
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
•
만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
•
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
•
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
풀이
•
기본 알고리즘
#Loop
1. 2차원 배열(Area)에서 시작
2. r, c 좌표가 현재 Area에서 몇사분면에 속하는지 파악
3. A 사분면에 속할 때 사분면 크기 * (A-1) 만큼의 값을 더해줌
# ex) 3사분면인 경우 1,2사분면을 지나온 것이 확실하기 때문에 해당 값을 누적
4. Area를 해당 A사분면으로 바꿔줌
Python
복사
•
입력
N, r, c = input().split()
N = int(N)
Python
복사
•
Square 함수 (사분면 판단)
- size = Area의 한 변의 길이
- x, y = Area의 시작 x, y 좌표
- r, c = target x,y 좌표
def square(size, x, y, r, c):
if (r < x + size/2):
if (c < y + size/2):
return 1
else:
return 2
else:
if (c < y + size/2):
return 3
else:
return 4
Python
복사
•
Main 동작
•
Area가 최소가 될때까지 사분면을 찾아 누적값을 더하고, Area의 시작 좌표와 Size를 조정한다.
startx, starty, result = 0,0,0 #시작 Area의 초기화
while N > 0:
size = 2 ** int(N) # Area의 한 변의 길이
pos = square(size, startx, starty, int(r),int(c)) # 사분면 찾기
sumsize = int((size/2) ** 2)
if pos == 2:
starty += size/2
result += sumsize
elif pos ==3:
startx += size/2
result += sumsize * 2
elif pos == 4:
startx += size/2
starty += size/2
result += sumsize * 3
N -= 1
print(result)
Python
복사
