문제 링크
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
풀이
- 분할 정복 문제인 줄 알고 재귀로 풀었는데 몇번째로 방문하는지 순서를 계산하는데에서 막혀 다른 블로그에서 아이디어를 얻고 풀었다.
- 사분면을 기준으로 좌표와 좌표에 해당하는 값을 수정해주면 되었다.
- 좌표 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)
'개발 > algorithm' 카테고리의 다른 글
[백준 1992번] 쿼드트리 -python (0) | 2022.02.16 |
---|---|
[백준 1697번] 숨바꼭질 - python (0) | 2022.02.16 |
[백준 18870번] 좌표 압축 - python (0) | 2022.02.15 |
[백준 1931번] 회의실 배정 - python (0) | 2022.02.15 |
[백준 1780번] 종이의 개수 - python (0) | 2022.02.15 |