algorithms

1차 시도

Comparing result with enum in python를 참고하여 r, c값과 배열의 크기를 서로 비교해 몇사분면에 위치해 있는지를 판단하는 코드를 작성했다.

def sol_recur(n: int, dim: int, r: int, c: int, lo: int, hi: int) -> int:
    if dim == 0:
        return lo
    cell_size = 2 ** (2 * dim - 2)
    match (compare(r, 2 ** (dim - 1)), compare(c, 2 ** (dim - 1))):
        case (Cmp.Less, Cmp.Less):
            # 1분면에 있음
            hi = lo + cell_size
        case (Cmp.Less, Cmp.Greater):
            # 2분면에 있음
            lo += cell_size
            hi = lo + cell_size
        case (Cmp.Greater, Cmp.Less):
            # 3분면에 있음
            lo += cell_size * 2
            hi = lo + cell_size
        case _:
            # 4분면에 있음
            lo += cell_size * 3
            hi = lo + cell_size
    return sol_recur(n, dim - 1, r, c, lo, hi)


n, r, c = [int(e) for e in input().split()]

print(sol_recur(n, n, r, c, 0, 2 ** (2 * n)))

하지만 결과는 칼같이 오답이었다. 😞

이유로 하여금 match 안에서 r, c값을 잘못 비교한 게 아닐까 싶기는 한데... 관심 Cell의 크기와 위치가 자꾸 바뀌니까 r, c도 계속 바꾸어야 함.

≤, <같은 equality도 고려해야겠구나 

Greater | Equal

≥ 사인이 없었기 때문에 계속 4분면으로 빠졌던 것이었다.

def sol_recur(dim: int, r: int, c: int, lo: int, hi: int) -> int:
    if dim == 0:
        return lo
    # 넓이와 변의 길이를 저장한다.
    side = 2**dim
    area = side**2
    # 각 분면의 넓이와 변의 길이를 저장한다.
    cell_side = side // 2
    cell_area = cell_side**2

    match (compare(r, cell_side), compare(c, cell_side)):
        case (Cmp.Less, Cmp.Less):
            # 1분면에 있음
            hi = lo + cell_area
        case (Cmp.Less, Cmp.Greater | Cmp.Equal):
            # 2분면에 있음
            lo += cell_area
            hi = lo + cell_area
            c -= cell_side
        case (Cmp.Greater | Cmp.Equal, Cmp.Less):
            # 3분면에 있음
            lo += cell_area * 2
            hi = lo + cell_area
            r -= cell_side
        case _:
            # 4분면에 있음
            lo += cell_area * 3
            hi = lo + cell_area
            r -= cell_side
            c -= cell_side
    return sol_recur(dim - 1, r, c, lo, hi)


if __name__ == "__main__":
    n, r, c = [int(e) for e in input().split()]

    print(sol_recur(n, r, c, 0, 2 ** (2 * n)))