[python]1074번 Z,최적화

시행착오가 많았던 문제였다. 생각하기 부터 구현까지 절차가 많았다

 

1생각

재귀를 기본으로 깔고 갔다. 이 기본적인 생각이 시간초과와 메모리초과의 근본이 되었다.

 

2생각

분할정복 느낌으로 1사분면,2사분면,3사분면,4사분면 모든 칸에 함수를 호출하여 4의 제곱의 횟수로 함수 호출을 하였다.

어쩐지 너무 느리더라

 

 

3생각

순번 값을 저장하기위해 함수들을 호출할때 마지막 칸 4**n 값을 기준으로 빼는 형식으로 할려다가

그보다는 0에서 부터 4**n씩 더해주는것이 편하다는 생각을 하였다.

 

4생각

사분면에 따라서 4**n에 상수를 곱하였다.

1사분면은 더하지 않고 그대로

2사분면은 4**n

3사분면은 4**n*2

4사분면은 4**n*3

왜냐하면 Z모양으로 사분면들을 이동하기에, 순서 또한 점차 늘어난다.

 

이제 생각을 끝내고 직접을 구현을 시도했다

 

1시도

모든 칸에 값들을 저장하는 리스트를 만들었다가 0% 메모리초과가 나면서 틀렸다.

 

2시도

모든 사분면에서 함수를 호출하니 시간초과가 나서

문제에서 원하는 칸에 해당하는 사분면만 함수 호출을 하여 연산량과 시간을 줄였다.

 

import sys
sys.setrecursionlimit(123456)
sze,row,clmn = map(int,input().split())
def find(num,x,y,start,row,clmn):
    if num>1:#최소 사각형이 될때까지 분해하기
        if clmn>=x+2**(num-1) and row>=y+2**(num-1):
            find(num-1,x+2**(num-1),y+2**(num-1),start+(4**(num-1)*3),row,clmn)
        elif clmn>=x+2**(num-1):
            find(num-1,x+2**(num-1),y,start+4**(num-1),row,clmn)
        elif row>=y+2**(num-1):
            find(num-1,x,y+2**(num-1),start+(4**(num-1)*2),row,clmn)
        else:
            find(num-1,x,y,start,row,clmn)
    else:#해당하는 칸에 도달했을 시
        rst = start #시작점
        for i in [(x,y),(x+1,y),(x,y+1),(x+1,y+1)]: #칸 순회
            if i[0] == clmn and i[1]==row: #해당하는 값
                print(rst) #출력
            rst+=1
find(sze,0,0,0,row,clmn)

나는 재귀로 풀어 비효율적이었지만

찾아보니 반복문으로 매우 효율적으로 해결한 풀이도 있어 공유합니다.

khykhy1006님의 풀이

https://www.acmicpc.net/source/54356669

로그인

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

ans = 0

while N != 0:

	N -= 1 #최소 사각형으로 분해,사분면 기준을 만들기

	# 1사분면
	if r < 2 ** N and c < 2 ** N:
		ans += ( 2 ** N ) * ( 2 ** N ) * 0 #값 유지

	# 2사분면
	elif r < 2 ** N and c >= 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 1 #값 갱신
		c -= ( 2 ** N ) #좌표 수정,현재 칸 크기와 맞추기 위해
        
	# 3사분면    
	elif r >= 2 ** N and c < 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 2
		r -= ( 2 ** N )
        
	# 4사분면    
	else:
		ans += ( 2 ** N ) * ( 2 ** N ) * 3
		r -= ( 2 ** N )
		c -= ( 2 ** N )
    
print(ans)