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)

 

아이패드에 좌표 엄청 그리면서 헤맸지만 조금 재미있었다