백준 1074번 z

딱봐도 분할정복하라는것같다.

분할정복을 하면서 순서대로 번호를 붙여나가고 r열 c행의 번호를 출력해주면 될것같다

 

import sys

n,r,c=map(int,sys.stdin.readline().rstrip().split())
graph=[[0]*(pow(2,n)) for _ in range(pow(2,n))]
count=[0]

def dfs(row,col,n):
    if n==1:
        graph[row][col]=count[0]
        count[0]+=1
        return
    dfs(row,col,n//2)
    dfs(row,col+n//2,n//2)
    dfs(row+n//2,col,n//2)
    dfs(row+n//2,col+n//2,n//2)
dfs(0,0,pow(2,n))
print(graph[r][c])

일단 이렇게 작성했는데 이대로 내면 매우 높은 확률로 시간초과가 날거다.

 

n이 15까지 입력될 수 있는데 그러면 30000정도 된다고 생각해야한다.

맵 사이즈가 3*10^4*3*10^4이므로 9*10^8 따라서 10^9정도라고 생각해야한다.

심지어 시간제한도 빡빡하게 줬다.

 

이 규칙을 이용하면 뭔가 될거같다.

import sys

n,r,c=map(int,sys.stdin.readline().rstrip().split())
result=0
def dfs(row,col,n):
    global r,c,result
    if n==1:
        print(result)
        return
    if r<row+n//2:
        if c<col+n//2:
            dfs(row,col,n//2)
        else:
            result+=(n//2*n//2)
            dfs(row,col+n//2,n//2)
    else:
        if c<col+n//2:
            result+=((n//2*n//2)*2)
            dfs(row+n//2,col,n//2)
        else:
            result+=((n//2*n//2)*3)
            dfs(row+n//2,col+n//2,n//2)
    
dfs(0,0,pow(2,n))

사분면으로 나눠서 생각을 한뒤에 첫번째 사분면은 그냥 가면 되고 나머지의 경우 번호를 알아내야하니까 나머지 사분면의 크기를 구한다음에 result에 더한다.