문제 링크

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

문제 설명

• 2차원 배열을 Z모양으로 탐색할 때 주어진 (r,c) 좌표가 몇 번째로 탐색하는지 구하는 문제

틀린 풀이

• 첫 좌표의 인덱스와 마지막 좌표의 인덱스를 가지고 재귀적으로 2차원 배열에 모든 순서를 저장하려 했으나 메모리 초과
• 2**n 단위로 메모리를 사용하기 때문인 것 같다
• 저장만 안 하고 값만 전달해볼까 했는데 이건 시간초과
• 하고보니 당연한 결과인 것 같다

맞은 풀이

• 모든 사분면에 대해 재귀적으로 함수를 호출해서 그런 것 같다
• r, c가 속한 사분면에 대해서만 재귀
• 그러려면 값을 계산해서 전달해야 한다
• 그러기 위해 현재 사분면의 좌표 개수, 첫번째 값을 인자에 추가로 넣었다
• 물론 좌표 개수는 인덱스 범위를 계산해서 구할 수도 있겠지만 계산이 복잡해지니 그냥 추가하는게 나은 것 같다

코드

def init():
    n, r, c = map(int, input().split())
    return n, r, c, -1


def find_num(start, end, total, first_value):
    global ans
    sy, sx = start
    ey, ex = end
    if sy+1 == ey and sx+1 == ex:
        if sy==r and sx==c:
            ans = first_value
        elif sy==r and sx+1==c:
            ans = first_value+1
        elif sy+1==r and sx==c:
            ans = first_value+2
        else:
            ans = first_value+3
        return
    if sy <= r <= (sy+ey)//2:
        if sx <= c <= (sx+ex)//2:
            find_num((sy, sx), ((sy+ey)//2, (sx+ex)//2), total//4, first_value+total//4*0)
        else:
            find_num((sy, (sx+ex)//2+1), ((sy+ey)//2, ex), total//4, first_value+total//4*1)
    else:
        if sx <= c <= (sx+ex)//2:
            find_num(((sy+ey)//2+1, sx), (ey, (sx+ex)//2), total//4, first_value+total//4*2)
        else:
            find_num(((sy+ey)//2+1, (sx+ex)//2+1), (ey, ex), total//4, first_value+total//4*3)


n, r, c, ans = init()
find_num((0, 0), (2**n-1, 2**n-1), (2**n)**2, 0)
print(ans)