[백준] 1074. Z / python 파이썬

🚩 분할정복, 재귀함수

 

thinking

처음에 4부분으로 쪼개고 카운팅했는데 output은 맞게 나왔으나 시간초과가 떴다.

시간초과를 줄이고자 마지막 else문의 범위를 나눴더니 패쓰됐다..

 

코드 (pass)

def divide(s_x, s_y, N):
    global cnt
    if N == 2:
        if s_x == r and s_y == c:  # 1위치
            print(cnt)
            return
        if s_x == r and s_y+1 == c:  # 2위치
            cnt += 1
            print(cnt)
            return
        if s_x+1 == r and s_y == c:  # 3위치
            cnt += 2
            print(cnt)
            return
        if s_x+1 == r and s_y+1 == c:  # 4위치
            cnt += 3
            print(cnt)
            return
        else:
            cnt += 4
            return
    else:
        half = N // 2
        if s_x <= r < s_x + half and s_y <= c < s_y + half:  # 1사분면
            divide(s_x, s_y, half)
        elif s_x <= r < s_x + half and s_y + half <= c < s_y + 2*half:  # 2사분면
            cnt += half*half
            divide(s_x, s_y + half, half)
        elif s_x + half <= r < s_x + 2*half and s_y <= c < s_y + half:  # 3사분면
            cnt += half*half*2
            divide(s_x + half, s_y, half)
        elif s_x + half <= r < s_x + 2*half and s_y + half <= c < s_y + 2*half:  # 4사분면
            cnt += half*half*3
            divide(s_x + half, s_y + half, half)


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

cnt = 0
divide(0,0,2**N)

 

시간초과 난 코드 (fail)

def divide(s_x, s_y, N):
    global cnt
    if N == 2:
        if s_x == r and s_y == c:  # 1위치
            print(cnt)
            return
        if s_x == r and s_y+1 == c:  # 2위치
            cnt += 1
            print(cnt)
            return
        if s_x+1 == r and s_y == c:  # 3위치
            cnt += 2
            print(cnt)
            return
        if s_x+1 == r and s_y+1 == c:  # 4위치
            cnt += 3
            print(cnt)
            return
        else:
            cnt += 4
            return
    else:
        divide(s_x, s_y, N // 2)
        divide(s_x, s_y + N // 2, N // 2)
        divide(s_x + N // 2, s_y, N // 2)
        divide(s_x + N // 2, s_y + N // 2, N // 2)


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

cnt = 0
divide(0,0,2**N)

 

 

한줄후기

알고리즘 문제라기보다 수학문제 같았던.. 노가다의 향연이었음