[BOJ_1074] Z

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

1074번: Z

 

생각한 알고리즘 : 재귀를 통한 분할정복

 

1차 생각 : 가로 2 ** n, 세로 2 ** n 의 이차원배열 maps을 만들어 칸에 맞는 숫자를 넣어 maps[r][c] 를 찾자!

# 메모리초과
def conquer(n, si, sj):
    global cnt, maps
    if n == 2:
       for i in range(si, si+2):
           for j in range(sj, sj+2):
               maps[i][j] = cnt
               cnt += 1
       return
    else:
        conquer(n//2, si, sj)
        conquer(n//2, si, sj+(n//2))
        conquer(n//2, si+(n//2), sj)
        conquer(n//2, si+(n//2), sj+(n//2))

N, r, c = map(int, input().split())
maps = [[0] * (2**N) for _ in range(2**N)]
cnt = 0
conquer(2**N, 0, 0)
print(maps[r][c])

결과 : 메모리초과

이유 : 배열의 크기가 너무 크기 때문에 메모리초과가 난 것 같다.

 

2차생각 : (2 ** n) * (2 ** n) 이차원배열을 모두 만들어서 볼 게 아니라, 2*2 이차원배열을 갱신한다.

r,c 값이 범위안에 들어오면 flag를 통해 conquer함수를 그만 돌도록 한다. (지금 생각해보니까 map의 크기만 줄였고, 함수를 도는 시간는 maps[r][c]를 찾을때까지만큼만 줄어들 뿐 거의 똑같은 함수인 것 같다.)

# 시간초과
def conquer(n, si, sj):
    global cnt, maps, flag
    if flag:
        return
    if n == 2:
        for i in range(2):
           for j in range(2):
               maps[i][j] = cnt
               cnt += 1
        if si <= r < si+2 and sj <= c < sj + 2:
            flag = True
        return
    else:
        conquer(n//2, si, sj)
        conquer(n//2, si, sj+(n//2))
        conquer(n//2, si+(n//2), sj)
        conquer(n//2, si+(n//2), sj+(n//2))

N, r, c = map(int, input().split())
maps = [[0] * (2) for _ in range(2)]
cnt = 0
flag = False
conquer(2**N, 0, 0)
r = r % 2
c = c % 2
print(maps[r][c])

결과 : 시간초과

이유 : 4번 재귀를 호출하기 때문에, N이 최대 15일 때, 최악의 경우 4^14번 함수를 호출한다. 절대 시간내로 초과할 수 없다.

 

3차생각 : 맵을 만들어서 찾지말고, r과 c의 인덱스 값만으로 재귀를 돌 수 있는 지 생각해보자.

사실 2**N maps을 4분할 했을 때 maps[r][c]가 포함된 사분면만 보면 되기 때문에 if문을 통해서 재귀를 줄일 수 있다.

또한 분할된 사분면의 첫번째값만 알면된다. 앞선 사분면의 칸수만큼 더해지는 규칙이 있기 때문이다.

 2사분면의 첫번째값 : 더해지는 값이 없다

 1사분면의 첫번째값 : 2사분면의 칸수만큼 더해진다.

 3사분면의 첫번째값 : 1, 2사분면의 칸수만큼 더해진다.

 4사분면의 첫번째값 : 1, 2, 3사분면의 칸수만큼 더해진다.

def conquer(N, r, c, cnt):
    if N == 2:
        # 숫자출력
        if r == 0 and c == 0:
            print(cnt)
        elif r == 0 and c == 1:
            print(cnt+1)
        elif r == 1 and c == 0:
            print(cnt+2)
        elif r == 1 and c == 1:
            print(cnt+3)
        return
    # (0, 0) (0, 4) (4, 0) (4, 4)
    n = N//2
    num = n**2
    if r < n and c < n:
        # 2사분면
        conquer(n, r, c, cnt)
    elif r < n and c >= n:
        # 1사분면
        conquer(n, r, c-n, cnt + num)
    elif r >= n and c < n:
        # 3사분면
        conquer(n, r-n, c, cnt + num*2)
    elif r >= n and c >= n:
        # 4사분면
        conquer(n, r-n, c-n, cnt + num*3)
        
N, r, c = map(int, input().split())
# 첫번째값만 가져와
conquer(2**N, r, c, 0)

결과: 통과

 

배운점 : 굳이 맵을 사용하지 않고 구현할 수 있는지 확인하자! 분기점을 통해서 재귀를 줄일 수 있도록 하자!