파이썬 알고리즘 231번 | [백준 1074번] Z

231. Z

1) 어떤 전략(알고리즘)으로 해결?

• 분할탐색

2) 코딩 설명

<내 풀이>

참고 풀이 :

< 내 틀렸던 풀이, 문제점>

시간초과!

• 질문 검색 ! https://www.acmicpc.net/board/view/64976

  전부 탐색하지 마시고 사각형을 4개로 나눠 위치에 따라서 한 사분면을 선택해 나가면서 재귀해보세요

라는 답변이! 오케이 ~

import sys
n, r, c = map(int,sys.stdin.readline().strip().split())

seq = []
seq = [list(-1 for _ in range(2**n)) for _ in range(2**n)]

def recur ( r, c, width , parent) :
    if width > 2 :
        recur(r,    c,      width//2, 4*parent + 0)
        recur(r,    c+width//2,     width//2, 4*parent + 1)
        recur(r+width//2,   c,      width//2, 4*parent + 2)
        recur(r+width//2,   c+width//2,     width//2,   4*parent + 3)

    elif width==2 and 0<=r<2**n and 0<=c<2**n : # width가 2가 되는 순간에는 이제 seq 에 기록
        #print(r,c)
        seq[r][c] = 4*parent + 0
        seq[r][c+1] = 4*parent + 1
        seq[r+1][c] = 4*parent + 2
        seq[r+1][c+1] = 4*parent + 3

recur(0,0,2**n*2**n,0)

print(seq[r][c])

import sys
n, r, c = map(int,sys.stdin.readline().strip().split())

seq = []
seq = [list(-1 for _ in range(2**n)) for _ in range(2**n)]

def recur ( r, c, width , parent) :
    if width > 2 :
        recur(r,    c,      width//2, 4*parent + 0)
        recur(r,    c+width//2,     width//2, 4*parent + 1)
        recur(r+width//2,   c,      width//2, 4*parent + 2)
        recur(r+width//2,   c+width//2,     width//2,   4*parent + 3)

    elif width==2 and 0<=r<2**n and 0<=c<2**n : # width가 2가 되는 순간에는 이제 seq 에 기록
        #print(r,c)
        seq[r][c] = 4*parent + 0
        seq[r][c+1] = 4*parent + 1
        seq[r+1][c] = 4*parent + 2
        seq[r+1][c+1] = 4*parent + 3

recur(0,0,2**n*2**n,0)

print(seq[r][c])

<반성 점>

<배운 점>