백준 1074 Z Python

🐸 문제 정보

1074번: Z

 

🤖 알고리즘

분할정복

 

⏱️ 풀이 시간

35.34m

 

📝 풀이

진짜 정말 오랜만에 분할정복 문제였다.

상당히 오래 고민하고... 종이에 많이 적어보면서 풀었다.

우선 기본적인 풀이 흐름은 아래와 같다.

 

1. 주어진 그래프를 4등분으로 분할
2. r, c 위치가 어디에 있는지 확인 후, 해당 사분면 이전의 사분면에 속한 수의 개수 더하기
3. r, c 위치를 분할된 그래프에 맞게 갱신
4. n이 1이 될 때 까지 반복

이제 흐름에 따라 자세한 방법과 식은 아래와 같다.

1. 분할 할 때 기준선은 2^(n-1) 이다.
   • 가령 n이 3일때, 한 변의 길이가 8이기 때문에
   • 4를 기준으로 작다면 왼쪽, 크거나 같다면 오른쪽이 된다.
2. r과 c의 위치는 기준선을 통해 알 수 있다.
   • 총 4등분을 기준으로 [[0, 1], [1, 2]] 이런 순서가 나오기 때문에, 1사분면 ~ 4사분면으로 분리했다.
   • 사분면 한 칸에 들어가는 수의 개수는 (2^(n - 1)) * (2^(n - 1)) 이기 떄문에, 2^(2n - 2)가 된다.
3. r과 c의 값은 속한 사분면에 따라 달라진다.
   • 1사분면
     • 원본 유지
   • 2사분면
     • r은 유지, c는 기준선의 값을 빼준다.
   • 3사분면
     • r은 기준선의 값을 빼주고, c는 유지
   • 4사분면
     • r과 c에 기준선의 값을 빼준다.
4. 최종적으로 n이 1인 경우 갱신된 r과 c의 값을 구했을 때, [[0, 1], [1, 2]] 이 중 어디에 속하는지 파악해서 더한다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, r, c = list(map(int, input().rstrip().split()))
stand = [[0, 1], [2, 3]]
res = 0

while n != 1:
    line = 2 ** (n - 1)
    frame = 2 ** (2 * n - 2)
    if r < line: # 1사분면은 변함 없음
        if c >= line: # 2사분면
            c -= line
            res += frame
    else:
        if c < line: # 3사분면
            r -= line
            res += (frame * 2)
        else: # 4사분면
            r -= line
            c -= line
            res += (frame * 3)
    n -= 1

res += stand[r][c]
print(res)