(Python)백준 코딩테스트 연습 - Z(1074)

1. 문제

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

1074번: Z

2. 풀이

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())

baseNum = 0
rStrIdx = 0
rEndIdx = (2 ** n) - 1
cStrIdx = 0
cEndIdx = (2 ** n) - 1
while True:
    if n == 1:
        break
    if rStrIdx <= r and r < rStrIdx + 2 ** (n - 1):
        rEndIdx -= (2 ** (n - 1))
        if cStrIdx <= c and c < cStrIdx + 2 ** (n - 1):
            cEndIdx -= (2 ** (n - 1))
        else:
            cStrIdx += (2 ** (n - 1))
            baseNum += (4 ** (n - 1))
    else:
        rStrIdx += (2 ** (n - 1))
        if cStrIdx <= c and c < cStrIdx + 2 ** (n - 1):
            cEndIdx -= (2 ** (n - 1)) - 1
            baseNum += (4 ** (n - 1)) * 2
        else:
            cStrIdx += (2 ** (n - 1))
            baseNum += (4 ** (n - 1)) * 3
    n -= 1
if rStrIdx != r:
    baseNum += 2
if cStrIdx != c:
    baseNum += 1
print(baseNum)

3. FeedBack

 - 이 문제는 분할 정복 알고리즘을 처음으로 사용했던 문제이다.

 분할 정복 알고리즘의 기본 개념이 방대한 문제를 단위별로 해결하는 것이기 때문에 위 문제의 해결도 동일하게 진행하였다.

 전체적인 코드의 흐름은 주어지는 2의 제곱 크기의 이차원 배열을 한번 탐색할 때마다 이전 제곱 크기의 -1 제곱 크기로 줄여가며 탐색을 진행하는 방식이다.

 다만, 분할 정복 알고리즘을 처음 개발하다보니 맞는 방식으로 코드를 구성했는지 의문은 있다.

 혹시 지나가던 개발 고수님이 계시다면 위 코드에 대한 댓글로 의견을 달아주신다면 감사하겠습니다.