[파이썬]백준 1074 Z

링크

백준 1074 Z

---

분할정복문제인줄 알았다.. 처음엔 문제를 보고 단순히 자식이 4개인 트리를 순회하도록 재귀로 구현했는데 시간초과로 실패했다.. 아니 누가봐도 분할정복인데 재귀가 시간초과가 나면 어떻게 하라는거지..? 싶어서 검색해서 아이디어를 얻고 풀수있었다 ㅜ
분할정복이긴 한데 뭐랄까 수학문제에 더 가까운 느낌..

---

찾아야 하는 좌표가 주어지니 전체 매트릭스에서 해당 좌표가 어느 사분면에 있는지 계산하며 찾아가는 방식으로 풀 수 있다.

N은 최대 탐색횟수가 되며
Z 순서대로 2사분면, 1사분면, 3사분면, 4사분면 순으로 탐색하며 해당 사분면을 기준으로 좌표를 수정해주면 된다.

2사분면의 경우 좌표를 따로 수정할 필요가 없다.

1사분면은 c를 크기만큼 빼주어 좌표를수정해준다. 또한 2사분면으로 이동하기 위해선 1사분면에 해당하는 갯수만큼 이동해야 하므로 size ** 2 를 더해준다.

3사분면은 r을 크기만큼 빼주어 좌표를 수정해준다. 또한 2사분면으로 이동하기 위해선 2, 1 사분면에 해당하는 갯수만큼 이동해야 하므로 size ** 2 를 2번 더해준다.

4사분면은 r과 c를 크기만큼 빼주어 좌표를 수정해준다. 또한, 4사분면으로 이동하기 위해선 2, 1, 3 사분면에 해당하는 갯수 만큼 이동해야 하므로 siez ** 2 를 3번 더해준다.

N이 1이되면 총 4칸을 갖고 있는 매트릭스가 남게 된다.
각 사분면에 맞는 좌표에 따라 값을 출력하면 된다.

---

오답 코드

def div_con(start_r, start_c, size):
    global cnt
    if size == 2:
        if start_r == r and start_c == c: # 2사분면
            print(cnt)
            return
        cnt += 1
        if start_r == r and start_c + 1 == c: # 1사분면
            print(cnt)
            return
        cnt += 1
        if start_r + 1 == r and start_c == c: # 3사분면
            print(cnt)
            return
        cnt += 1
        if start_r + 1 == r and start_c + 1 == c: # 4사분면
            print(cnt)
            return
        cnt += 1
    else:
        size //= 2
        div_con(start_r, start_c, size) # 2사분면
        div_con(start_r, start_c + size, size) # 1사분면
        div_con(start_r + size, start_c, size) # 3사분면
        div_con(start_r + size, start_c + size, size) # 4사분면

N, r, c = map(int, input().split())
cnt = 0

div_con(0, 0, 2 ** N)

---

정답 코드

N, r, c = map(int, input().split())
cnt = 0

while N > 1:
    size = (2 ** N) // 2
    if r < size and c < size: # 2사분면
        pass
    elif r < size and c >= size: # 1사분면
        cnt += size ** 2
        c -= size
    elif r >= size and c < size: # 3사분면
        cnt += size ** 2 * 2
        r -= size
    elif r >= size and c >= size: # 4사분면
        cnt += size ** 2 * 3
        r -= size
        c -= size
    N -= 1

if r == 0 and c == 0:
    print(cnt)
if r == 0 and c == 1:
    print(cnt + 1)
if r == 1 and c == 0:
    print(cnt + 2)
if r == 1 and c == 1:
    print(cnt + 3)

---

알게된 것👨‍💻

• 전형적인 문제라 생각 말고 더 좋은 방법이 있는지 고민해보자