[파이썬] 백준 1074 : Z (실버1)

[파이썬] 백준 1074 : Z (실버1)

 

1074번: Z

---

문제

---

풀이

0.방향성 생각

위 예시처럼 n = 3인 경우 43 (7행 1열)을 찾는다고 가정해보자.

0,0에서 시작해서 탐색을 진행한다. 탐색하려는 좌표의 사분면을 찾는다.

그 사분면 기준점으로 이동해서 재귀함수를 호출한다.

 

1. 전체 코드

import sys
sys.setrecursionlimit(10**6)

n,row,col = map(int,input().split())

def z(h,w,N):
    if row == h and col == w:
        return 0

    b = 2**(N-1)  # 좌표 옮길 때 idx 값 변화, 사각형 절반 길이

    if row < h+b:
        if col < w+b:  # 2사분면
            return z(h,w,N-1)
        else:  # 1사분면
            return b*b+z(h,w+b,N-1)
    else:
        if col < w+b:  # 3사분면
            return 2*b*b+z(h+b,w,N-1)
        else:  # 4사분면
            return 3*b*b+z(h+b,w+b,N-1)

print(z(0,0,n))

DFS에서 카운트하듯이 재귀함수 내에서 추가적인 정보를 주지 않고 리턴값에 계속 더해주는 식으로 작성한다.

---

오답 코드

n,row,col = map(int,input().split())

def z(num,h,w,N):
    if row==h and col==w :
        return num

    a = 2**(2*(N-1))  # 좌표 옮길 때 num 값 변화
    b = 2**(N-1)  # 좌표 옮길 때 idx 값 변화, 사각형 절반 길이

    if row<b :
        if col<b : # 2사분면
            return z(num,h,w,N-1)
        else : # 1사분면
            return z(num+a,h,w+b,N-1)
    else : 
        if col<b: # 3사분면
            return z(num+2*a,h+b,w,N-1)
        else: # 4사분면
            return z(num+3*a,h+b,w+b,N-1)

print(z(0,0,0,n))

1. 목표지점 row, col을 받는다.

2. 좌표이동 시 값을 계산하기 위한 a, 좌표이동 시 인덱스를 계산하기 위한 b를 정의한다.

3. row<b, 즉 사각형의 위에 위치했을 때, 좌측에 있으면 2사분면에 위치하므로 자기 자신 위치에서 사각형 줄이고 재귀

같은 방법으로 사분면에서 재귀를 진행한다.

여기서 num이 계속 호출돼서 메모리초과가 나버림

 

코멘트

구현은 어렵진 않았는데 시간 메모리 줄이는 생각 하다보니까 DFS 재귀 이해도도 올라간듯