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

첫번째 시도

메모리 초과

전체 판을 생성해서 순서대로 번호를 다 넣어서 완성하고

그 자리를 참조하여 알아내는 방식으로 만들었다. 이론적으로는 다 맞는데 왜 메모리초과가 나는지 이해를 하지 못했다.

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

arr  = [[0] * (2**N) for _ in range((2**N))]

cnt =0
    
def func(start, end ) : # start pt(왼쪽상단), end pt 오른쪽하단
    # start = (x, y)
    # end = (x, y)
    
    diff = end[0] -start[0] +1 # 주어진 블록의 크기

    if diff == 1 :
        global cnt # 왠만하면 쓰기 싫은데..
        arr[start[1]][start[0]] = cnt
        cnt+=1
        return

    half = diff //2
    
    move_x = (0, half, 0, half)
    move_y = (0, 0, half, half)

    for i in range(4) :
        next_start_x = start[0] + move_x[i]
        next_start_y = start[1] + move_y[i]
        next_start = (next_start_x, next_start_y)

        next_end_x = next_start_x + half- 1
        next_end_y = next_start_y + half -1
        next_end = (next_end_x, next_end_y)

        func(next_start, next_end)

start = (0,0)
end = (2**N-1, 2**N-1)
func(start, end)
print(arr[r][c])

두번째 시도

• 해결시도
  • diff ==1 이라서 재귀 깊이가 너무 깊어서 계산이 많이됬나? 싶어서 diff==2로 올려서 재귀 깊이를 제곱근으로 줄어들게함
  • 또한 계속 start, end 좌표를 넣은 tuple과 move_x, move_y 같은 변수들이 많이 생성되서 메모리가 터졌나? 싶어서 매개변수의 형식을 변경함

하지만 계속한 메모리 초과

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

arr  = [[0] * (2**N) for _ in range((2**N))]

cnt =0
    
def func(start_x, start_y, end_x, end_y ) : # start pt(왼쪽상단), end pt 오른쪽하단
    
    diff = end_x -start_x +1 # 주어진 블록의 크기

    if diff == 2 :
        global cnt # 왠만하면 쓰기 싫은데..
        
        arr[start_y][start_x] = cnt
        arr[start_y][start_x+1] = cnt+1
        arr[start_y+1][start_x] = cnt+2
        arr[start_y+1][start_x+1] = cnt+3
        cnt +=4

        return

    half = diff //2
    
    move_x = (0, half, 0, half)
    move_y = (0, 0, half, half)

    for i in range(4) :
        next_start_x = start_x + move_x[i]
        next_start_y = start_y + move_y[i]

        next_end_x = next_start_x + half- 1
        next_end_y = next_start_y + half -1


        func(next_start_x, next_start_y, next_end_x, next_end_y)

func(0,0, 2**N-1, 2**N-1)
print(arr[r][c])

세번째 시도

• 해결시도

  • 전체를 완성하려고 해서 그런게 아닐까? 라는 생각이 들었다. 그래서 arr[r][c] 이 포함된 부분만 재귀가 돌아가서 그 블럭만 계산이 되도록 하면 계산이 대폭 줄어들겠다는 생각이 들었다

    check1, check2를 만들어 arr[r][c] 포함 부분이 아니라면 cnt를 늘리고 스킵해버리게 만들었다.

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

arr  = [[0] * (2**N) for _ in range((2**N))]

cnt =0

    
def func(start_x, start_y, end_x, end_y ) : # start pt(왼쪽상단), end pt 오른쪽하단
    
    diff = end_x -start_x +1 # 주어진 블록의 크기
    global cnt # 왠만하면 쓰기 싫은데..

    check1 = start_x <= c <= end_x 
    check2 = start_y <= r <= end_y
    if not( check1 and check2 ) :
        cnt+= diff*diff
        return

    if diff == 2 :
        arr[start_y][start_x] = cnt
        arr[start_y][start_x+1] = cnt+1
        arr[start_y+1][start_x] = cnt+2
        arr[start_y+1][start_x+1] = cnt+3
        cnt +=4

        return

    half = diff //2
    
    move_x = (0, half, 0, half)
    move_y = (0, 0, half, half)

    for i in range(4) :
        next_start_x = start_x + move_x[i]
        next_start_y = start_y + move_y[i]

        next_end_x = next_start_x + half- 1
        next_end_y = next_start_y + half -1


        func(next_start_x, next_start_y, next_end_x, next_end_y)

func(0,0, 2**N-1, 2**N-1)
print(arr[r][c])

네번째 시도

• 해결시도
  • 도대체 왜 메모리 초과가 일어날까? 궁금해서 재귀의 깊이를 N= 20, 500, 500 으로 넣고 돌려봤다
    • arr = [[0] * (2**N) for _ in range((2**N))] 이 부분에서 메모리가 터지는 것을 repl.it 에서 확인했다.
  • N= 10, 500, 500 을 넣고 돌려본 결과 재귀 깊이가 30 이하로 그렇게 깊지 않은 것도 확인했다
  • 그리고 다시 코드를 확인해본 결과 굳이 arr이 없어도 잘 돌아갈 것 같다는 생각이 들었다. 그래서 제거했다.

드디어 성공.. 개같은거;

완성하고보니 result란 변수는 필요가 없다는 것을 알게되었다. cnt만으로 할 수 있었는데 왜 굳이 만들었을까..

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

# arr  = [[0] * (2**N) for _ in range((2**N))]
result =0
cnt =0

def func(start_x, start_y, end_x, end_y ) : # start pt(왼쪽상단), end pt 오른쪽하단
    global result

    diff = end_x -start_x +1 # 주어진 블록의 크기
    global cnt # 왠만하면 global 쓰기 싫은데..

    check1 = start_x <= c <= end_x 
    check2 = start_y <= r <= end_y
    if not( check1 and check2 ) :
        cnt+= diff*diff
        return

    if diff == 1 :
        if start_x==c and start_y ==r :
            result = cnt
        cnt+=1
    # if diff == 2 :
    #     arr[start_y][start_x] = cnt
    #     arr[start_y][start_x+1] = cnt+1
    #     arr[start_y+1][start_x] = cnt+2
    #     arr[start_y+1][start_x+1] = cnt+3
    #     cnt +=4

    #     return

    half = diff //2
    
    move_x = (0, half, 0, half)
    move_y = (0, 0, half, half)

    for i in range(4) :
        next_start_x = start_x + move_x[i]
        next_start_y = start_y + move_y[i]

        next_end_x = next_start_x + half- 1
        next_end_y = next_start_y + half -1


        func(next_start_x, next_start_y, next_end_x, next_end_y)

func(0,0, 2**N-1, 2**N-1)
print(result)