algorithm/DivideAndConquer
[백준1074/골드5] Z - Python
ayeongjin
2025. 3. 9. 21:41
https://www.acmicpc.net/problem/1074
문제 풀이 방식 생각하기까지 꽤 오래걸렸다.
처음 시작점을 (0, 0)으로 두고 0, 1, 2, 3 구역중에 위치를 찾아가면서 그 구역에 속하는 숫자들을 더하면서 새로운 시작점을 찾는 방식으로 풀어야겠다고 생각했다.
1. (0, 0) 부터 시작, 한변의 길이(n)이 1이 될 때 까지 반절로 자르면서 (r, c) 찾아가기
2. (r, c)가 0 구역에 속하면 지나친 숫자 없음 -> 한 변의 길이만 자르기
3. (r, c)가 1 구역에 속하면 0 구역의 숫자들 지나침 -> 0 구역에 속하는 칸들 다 지나치기 (result += (half * half))
4. (r, c)가 2 구역에 속하면 0, 1, 구역의 숫자들 지나침 -> 0, 1 구역에 속하는 칸들 다 지나치기 (result += (half * half) * 2)
5. (r, c)가 3 구역에 속하면 0, 1, 2 구역의 숫자들 지나침 -> 0, 1, 2 구역에 속하는 칸들 다 지나치기 (result += (half * half) * 3)
6. n == 1 이면 (r, c)에 도착 -> 그동안 지나친 영역의 개수 result 출력
'''
해당 구역까지 찾아가서 조금씩 숫자를 더하기
'''
N, r, c = map(int, input().split())
result = 0
def z(n, r, c, x, y):
global result
if n == 1:
print(result)
return
half = n // 2
# 0
if r < x + half and c < y + half:
z(half, r, c, x, y)
# 1
elif r < x + half and c >= y + half:
result += half * half
z(half, r, c, x, y + half)
# 2
elif r >= x + half and c < y + half:
result += half * half * 2
z(half, r, c, x + half, y)
# 3
else:
result += half * half * 3
z(half, r, c, x + half, y + half)
z(2**N, r, c, 0, 0)
아이패드에 좌표 엄청 그리면서 헤맸지만 조금 재미있었다