백준 알고리즘 파이썬(Python) 1074번 Z

---

r과 c가 주어진다면 차례로 어느 사분면에 있는지를 확인하여 문제를 풀어나간다.

(여기서 주의해야 할 점은 우리가 수학에서 흔히 배우는 오른쪽 위가 1 사분면인 사분면이 아니라 

문제에서 주어진 순서대로의 사분면이다.)

 

만약 우리가 찾는 좌표가 4사분면에 있다면 그 좌표는 이미 1, 2, 3 사분면은 거친 좌표이니 그에 맞는 숫자를 더해주고 생각하면 된다.

 

예를 들어 n = 3이고 r과 c가 각각 7이라고 하자

그렇다면 n = 3일 때 r과 c는 4 사분면에 있으므로 3 사분면까지의 숫자는 이미 거친 것이다.

그 말은 (4**2) * 3을 더해주고 새롭게 n = 2인 경우로 시작하면 된다는 뜻이다.

n = 2인 경우에도 r과 c는 3,3 즉 4 사분면에 존재한다. 아까와 같은 방식 즉 재귀의 방법으로

(2**2) *3을 더해주고 새롭게 n = 1인 경우에서 시작하면 된다.

 

마지막 n = 1인 경우에는 더 이상 4로 나누었을 때 사분면이라는 개념 자체가 사라지므로 

• 만약 r, c 가 (0, 0) 이라면 그대로
• (0, 1) 이라면 + 1
• (1, 0) 이라면 + 2
• (1, 1) 이라면 + 3

을 해줌으로써 기존에 쌓여왔던 num에 숫자를 추가하여 최종 답을 구하면 된다.

 

n, r, c = map(int, input().split())
num = 0
while n > 0:
    temp = (2 ** n) // 2
    if n > 1:
        # 2사분면에 있을 경우
        if temp > r and temp <= c: 
            num += temp ** 2
            c -= temp
        # 3사분면에 있을 경우
        elif temp <= r and temp > c:
            num += (temp ** 2) * 2
            r -= temp
        # 4사분면에 있을 경우
        elif temp <= r and temp <= c:
            num += (temp ** 2) * 3
            r -= temp
            c -= temp
    elif n == 1: #재귀용법을 써서 n=1 즉 2^1 x 2^1 만 남았을 때 1,2,3,4 분면에 차례로 0,1,2,3 을 더해준다.
        if r == 0 and c == 1:
            num += 1
        elif r == 1 and c == 0:
            num += 2
        elif r == 1 and c == 1:
            num += 3
    n -= 1
print(num)