백준 실버1 1074. Z (python)

Z

 

풀이

처음에 문제를 보고 도저히 어떻게 푸는지 감이 안왔다.. 일단 사람 머리로는 이해가 되는데 컴퓨터 머리로는 어떻게 하는지 모르겠더군.

근데 다음 처럼 내용이 나왔다.
위치 값을 표기한 것인데 아래처럼 위치 값이 표기되었다.

N = 0
[
[0,0]
]
N = 1
# 2**(1-0)만큼을 큰 틀에서 더 움직임
[
[0,0],

[0,1],

[1,0],

[1,1],
]
N = 2
# 2**(2-1)만큼을 큰 틀에서 더 움직임
[
[0,0],[0,1],[1,0],[1,1],

[0,2],[0,3],[1,2],[1,3],

[2,0],[2,1],[3,0],[3,1],

[2,2],[2,3],[3,2],[3,3],
]
N = 3
# 2**(3-1)만큼을 큰 틀에서 더 움직임
# N=2 의 값에서 열에 2**2, 행에 2**2, 행렬 2**2 더한 값을 추가.
[
[0,0],[0,1],[1,0],[1,1],
[0,2],[0,3],[1,2],[1,3],
[2,0],[2,1],[3,0],[3,1],
[2,2],[2,3],[3,2],[3,3],

[0,4],[0,5],[1,4],[1,5],
[0,6],[0,7],[1,6],[1,7],
[2,4],[2,5],[3,4],[3,5],
[2,6],[2,7],[3,6],[3,7],

[4,0],[4,1],[5,0],[5,1],
[4,2],[4,3],[5,2],[5,3],
[6,0],[6,1],[7,0],[7,1],
[6,2],[6,3],[7,2],[7,3],

[4,4],[4,5],[5,4],[5,5],
[4,6],[4,7],[5,6],[5,7],
[6,4],[6,5],[7,4],[7,5],
[6,6],[6,7],[7,6],[7,7],
]

N에서 나온 값은 N-1에서 나온 위치에서 2**(N-1)을 열에 더해준 값, 행에 더해준 값, 행렬에 더해준 값을 가지게 된다.
따라서 난 아래처럼 코드를 작성해봤다.
이 코드는 모든 행렬의 위치를 다 작성하고, 찾는 위치가 언제 들리게 되는지를 알 수 있게 하는 코드인 셈이다.

import sys
# nr 행에서 적용되는 N값, nc 열에서 적용되는 N값
# N-1 값을 완성시켜놔야함.
# def solution(nr,nc,row,column):
def solution(n):
    global board
    # 제곱수가 마직막으로 들어갔을 때 넣기
    if n == 0:
        board = [[0,0]]
        return
    else:
        solution(n-1)
        board_length = len(board)
        for i in range(board_length):
            board.append([board[i][0], board[i][1]+2**(n-1)])
        for j in range(board_length):
            board.append([board[j][0]+2**(n-1), board[j][1]])
        for k in range(board_length):
            board.append([board[k][0]+2**(n-1), board[k][1]+2**(n-1)])
    return

N,r,c = map(int, sys.stdin.readline().split())
board = []
answer = 0
solution(N)
print(board.index([r,c]))

문제는 확실히 맞는다. 틀리지도 않는다.
다만 문제가 있는데 시간이 오래 걸린다.

그래서 다른 방법을 찾아보니 아래와 같은 방법이 있었다.
분할 정복이라고 하더라.

현재의 나로서는 어떻게 풀어야할지 아무래도 감도 못잡는데, 덕분에 다시 눈이 띄었다. 이런 방법도 있었군.

이 방법은 재귀를 이용하지만, 4분면으로 나눠서 구분하는 방법을 이용했다.

내가 원래했던 방법은 어디에 위치해있던 상관없이 끝까지 끝까지 행렬을 다 만들고 나서 위치를 확인하지만, 이것은 그러지 않고, 1,2,3 사분면에 있다면, 딱 필요한 곳 까지만 만들고 끝내는 함수인 것이다.

따라서 내가 만든 함수와 개념은 동일하되 시간이 단축된다고 볼 수 있겠다. 특히 모두 1사분면에 있다면 더더욱 그렇다.

import sys

def solution(n, r, c):
    # 재귀함수 종료 조건
    if n == 0: 
        return 0

    half = 2**(n-1)  # 현재 그리드를 4등분 한 사이즈

    # (r, c)가 1사분면에 위치한 경우
    if r < half and c < half: 
        return solution(n-1, r, c)  # 1사분면 내에서 같은 패턴으로 탐색
    
    # (r, c)가 2사분면에 위치한 경우
    elif r < half and c >= half: 
        return half * half + solution(n-1, r, c - half)  # 1사분면 크기만큼 더하고 2사분면에서 같은 패턴으로 탐색
    
    # (r, c)가 3사분면에 위치한 경우
    elif r >= half and c < half: 
        return 2 * half * half + solution(n-1, r - half, c)  # 1사분면과 2사분면 크기만큼 더하고 3사분면에서 같은 패턴으로 탐색
    
    # (r, c)가 4사분면에 위치한 경우
    else: 
        return 3 * half * half + solution(n-1, r - half, c - half)  # 1사분면, 2사분면, 3사분면 크기만큼 더하고 4사분면에서 같은 패턴으로 탐색

N, r, c = map(int, sys.stdin.readline().split())
print(solution(N, r, c))  # 결과 출력