[백준] 1074번 Z 파이썬 풀이

https://www.acmicpc.net/problem/1074

1074번: Z

---

1. 접근 방식

• 방문하는 r행 c열이 위치하는 사분면에만 집중하자.

N = 3, r = 7, c = 7일 때를 예시를 들면 다음과 같다.

7행 7열은 첫 번째 그림에서 제 4사분면에 위치한다. 따라서 나머지 제 1, 2, 3사분면에 있는 임의의 칸을 몇 번째로 방문하는지는 알 필요가 없으며, 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 사실만 중요하다.

 

재귀를 통해 제 4사분면으로 들어가면, 다시 중간 그림처럼 배열이 세팅된다. 7행 7열은 이번에도 제 4사분면에 속하므로, 이것이 속한 제 4사분면이 60번째부터 방문한다는 것에 집중한다.

 

또 다시 재귀를 통해 제 4사분면으로 들어가자. 7행 7열은 이곳에서도 제 4사분면에 위치하므로, 제 4사분면이 63번째부터 방문한다는 것만 알면 된다.

 

다시 재귀를 통해 제 4사분면으로 들어가면, 배열의 크기가 1x1이다. 이는 재귀의 종료 조건으로, 정답 63을 반환하며 재귀를 끝낸다.

 

 

• 그럼 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 걸 어떻게 알 수 있을까?

제 4사분면 이전에 제 1, 2, 3사분면에 있는 칸을 모두 방문한다. 제 1사분면에 16칸, 제 2사분면에 16칸, 제 3사분면에 16칸이 존재하므로, 제 4사분면의 첫 번째 칸은 48번째로 방문됨을 알 수 있다.

 

 

 

2. 정답 코드

def fill_quadrants(exp, i, j, r, c):
    if exp == 0:
        return count[0]

    half = 2**(exp - 1)
    full = half * 2

    quadrants = [
        [(i, j), (i + half, j + half)],
        [(i, j + half), (i + half, j + full)],
        [(i + half, j), (i + full, j + half)],
        [(i + half, j + half), (i + full, j + full)]
    ]

    for start, end in quadrants:
        if start[0] <= r < end[0] and start[1] <= c < end[1]:
            return fill_quadrants(exp - 1, start[0], start[1], r, c)
        else:
            count[0] += half * half


n, r, c = map(int, input().split())
count = [0]

print(fill_quadrants(n, 0, 0, r, c))

 

추가로 다른 분들의 제출 답안을 불러보던 중 매우 효율적인 코드가 있어서 첨부한다.

https://www.acmicpc.net/source/65332006

로그인