BOJ 1074 "Z"

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

1074번: Z

 

핫쒸... 솔직히 처음엔 만만하게 봤는데 어려웠다.
알고리즘은 역시 평소에 꾸준히 안해두면 머리가 굳나보다...반성 반성...^,ㅠ

 

이 문제는 인덱스가 0부터 시작한다는 것과 재귀함수를 잘 사용해야 한다.
(내 코드는 너무 더러웠고 가장 깔끔해보이고 이해된 코드를 기준으로 작성함.)

이 문제는 0, 1, 2, 3 사분면(원래는 1부터 시작하지만 0부터라 하겠다), 각각을 네 개의 case로 쪼개서 푼 해설이 많은데

다음과 같이 풀면 하나의 케이스를 통해 해결할 수 있다.

 

# 백준에 제출할 때에는 물론 필요없는 print문 제거하고 해야합니다
def Z(sz, x, y):
    if sz == 1:
        return 0

    sz //= 2

    for i in range(2):
        for j in range(2):
            if x < sz * (i+1) and y < sz * (j+1):
                # 몇사분면에 들어오냐를 결정함
                # (0, 0)-> 1사분면, (0, 1) -> 2사분면, 
                # (1, 0) -> 3사분면, (1, 1) -> 4사분면
                # sz를 곱하는 건 해당 박스의 길이만큼 곱하여 몇 사분면에 위치하는지 알기 위함
                print((i*2+j), "사분면에 있음")
                print((i*2+j) * sz*sz, "만큼 지나옴")
                print()
                return (i*2+j) * sz*sz + Z(sz, x-sz*i, y-sz*j)


if __name__=="__main__":

    N, r, c = map(int, input().split())
    print(Z(2**N, r, c))
    print()

설명하기 위해 필요 없는 print문을 달아놨으니 한번 보자 미래의 나야.

 

먼저 2*i + j 가 의미하는 바는 처음에 입력된 r, c가 몇 사분면에 위치하는 포인트냐를 의미한다.

각 사분면의 값 = 2*i + j

 

재귀함수를 사용하는 것은 처음의 박스를 quadtree로 한번씩 쪼개면서 해당 포인트에 몇 번 만에 도달하느냐를 파악하기 위함이다.

이렇게 말하면 미래의 내가 그게 뭔데 씹덕아라고 할 것 같다.. 

 

2^3 * 2^3 크기의 박스에서 4행 3열의 값인 37을 찾는 과정을 보자

다시 말하지만 N행 M열이라 할 때 N, M은 0부터 시작한다. 1부터가 아님. 

 

 

 

37은 가장 처음 2사분면에 존재한다. 

해당 2사분면에 도달하기까지 32만큼을 지나온 것을 확인할 수 있다.

 

이전에 2사분면에 도달하기까지 32만큼 지나왔다.

그 다음의 작은 사각형에서 1사분면에 들어오기까지 4만큼 지나온 것을 확인할 수 있다.

 

 

2x2배열이 마지막이다. 자 이제 마지막으로 37이 위치한 1사분면까지 오기까지 1만큼 지나온 것을 확인할 수 있다.

 

 

지나온 만큼의 숫자 (32, 4, 1)들을 모두 더하면 37이 된 것을 확인할 수 있다. 

처음의 2^N x 2^N 배열을 가운데 기점으로 하나씩 쪼개면서 해당 포인트(r, c)가 위치한 사분면에 도달하기 까지를 재귀함수를 통해 구한 것이다.