[python] 백준 - 1074. Z

🤔문제 해결

1. 재귀,분할정복 | S1

2. 모두 쪼개려고 하는경우 메모리초과 혹은 시간초과가 발생한다.

3. 내가 찾고자하는 행과 열이 포함된 박스만 찾아서 재귀함수를 실행시킨다.

4. 여기서 각 박스의 첫 숫자를 구한다.

 (1) 예를 들어 사이즈가 8인 박스의 첫숫자는 0이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 박스를 쪼개면

 (2) 각 박스의 첫 숫자는 0, 16, 32, 46 이다.

 (3) 왼쪽 위 박스는 그대로, 오른쪽 위 박스는 첫숫자에 (size//2)**2*1 값을 더해준다.

 (4) 왼쪽 아래 박스는 첫숫자에 (size//2)**2*2 값을, 오른쪽 아래 박스는 첫숫자에 (size//2)**2*3 값을 더해준다.

5. 박스의 크기가 2가 되면 찾고자 하는 행과 열을 찾아서 해당 숫자를 출력한다.

 ( 박스의 크기가 1일때도 가능하지만 재귀 깊이를 줄이기 위해 )

 

💨 처음에 모든박스를 쪼개고 숫자를 하나하나 채워가면서 구했더니 답은 나오지만 메모리 초과가 발생했다.

그 다음 방법으로는 모든 박스 쪼개고 적당히 숫자를 때려맞췄지만 시간초과 발생.

마지막으로 내가 원하는 박스만 찾아들어가고 규칙을 알아내서 값을 구해서 통과 - 난이도에 비해 너무 오래걸렸다...

 

💻소스 코드

def Z(row, col, size, num): # (row,col: 자른 box의 첫번째 인덱스, size: box 사이즈, num: box 시작점의 숫자)
    if size == 2: # 사이즈가 2x2가 됐을 때
        if row == r and col == c:
            print(num)
            return
        num += 1

        if row == r and col + 1 == c:
            print(num)
            return
        num += 1

        if row + 1 == r and col == c:
            print(num)
            return
        num += 1

        if row + 1 == r and col + 1 == c:
            print(num)
            return
        num += 1

    else:
        half_size = size // 2
        # 왼쪽 위
        if row <= r < row + half_size and col <= c < col + half_size:
            Z(row, col, half_size, num)
        # 오른쪽 위
        elif row <= r < row + half_size and col + half_size <= c < col + size:
            Z(row, col + half_size, half_size, num + (half_size ** 2) * 1)
        # 왼쪽 아래
        elif row + half_size <= r < row + half_size * 2 and col <= c < col + half_size:
            Z(row + half_size, col, half_size, num + (half_size ** 2) * 2)
        # 오른쪽 아래
        elif row + half_size <= r < row + half_size * 2 and col + half_size <= c < col + size:
            Z(row + half_size, col + half_size, half_size, num + (half_size ** 2) * 3)


if __name__ == "__main__":
    N, r, c = map(int, input().split())
    Z(0, 0, 2 ** N, 0)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1074번: Z

---

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.