IT/ps
백준 1074번 z
u149_cinderella
2025. 2. 16. 02:04
딱봐도 분할정복하라는것같다.
분할정복을 하면서 순서대로 번호를 붙여나가고 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에 더한다.