Problem Solving/Online Judge
[BOJ] #1074 - Z
se0m
2021. 6. 15. 01:58
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서
www.acmicpc.net
** 문제 유형
- 재귀 함수, 분할 정복
** 풀이
- Z 모양을 구성하는 4가지 방향에 대하여 차례대로 재귀적으로 호출
def sol(n, r, c):
global result
if n == 2:
if r == R and c == C:
print(result)
return
result += 1
if r == R and c + 1 == C:
print(result)
return
result += 1
if r + 1 == R and c == C:
print(result)
return
result += 1
if r + 1 == R and c + 1 == C:
print(result)
return
result += 1
return
sol(n / 2, r, c)
sol(n / 2, r, c + n / 2)
sol(n / 2, r + n / 2, c)
sol(n / 2, r + n / 2, c + n / 2)
N, R, C = map(int, input().split(' '))
result = 0
sol(2 ** N, 0, 0)
-> 시간 초과
def divide(n, x, y):
global result
if x == r and y == c:
print(result)
return
if x <= r < x + n and y <= c < y + n: # 찾는 위치(r, c)가 해당 범위에 포함될 경우
divide(n//2, x, y)
divide(n//2, x, y + n//2)
divide(n//2, x + n//2, y)
divide(n//2, x + n//2, y + n//2)
else:
result += n * n
n, r, c = map(int, input().split())
result = 0
divide(2**n, 0, 0)
-> 해결