[백준] 1074번: Z

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

initial

I followed this divide and conquer logic in this link
https://ggasoon2.tistory.com/11

I drew it out and you can divide any graph into 4 quadrants. Each quadrant's 0th element is increment by 2^(n-1) times 2^(n-1). For example when n=2, the first quadrant's 0th element is 0 (2^1 times 2^1 times 0), second quadrant's 0th element is 4 (2^1 times 2^1 times 1) and 3rd quadrant is 8 (2^1 times 2^1 times 2) and finally the 4th quad is 12 (2^1 times 2^1 times 3).

Then, depending on which quadrant this initial row and column is, we have to deduce the next row and column for a smaller n. For example, if it is in 3rd quad, then for the next iteration of n-1, r has to be deducted by 2**n much for the logic to work. we do it till n==0.

solution

ans=0
n,r,c = map(int,input().split())
while n>=1:
    n-=1
    # 1st quadrant
    if r<2**n and c<2**n:
        ans += (2**n) * (2**n) *0
    # 2nd quadrant
    if r<2**n and c>=2**n:
        ans += (2**n) * (2**n) *1
        c-= 2**n
    # 3rd quad
    if r>=2**n and c<2**n:
        r-= 2**n
        ans += (2**n) * (2**n) *2
    # 4th quad
    if r>=2**n and c>=2**n:
        ans += (2**n) * (2**n) *3
        r-= 2**n
        c-= 2**n
print(ans)

complexity

n time and space cuz it repeats n times from n until n becomes 0