[PS | 한 번에 맞자!] 백준 1074

0. 문제

Z

1074번: Z

---

1. 문제 설명

크기가 2^N X 2^N 모양 배열을 Z 모양으로 탐색하려고 할 때 R행 C열을 몇 번째로 방문하는지 찾아내는 문제이다. 규칙이 보이기 시작했고, 분할정복으로 채워나가며 추적하는 방법을 사용하려고 하였다. 

---

2. 문제 구현

처음 시간초과 코드

N,R,C=map(int,input().split())
turn=1
def divide_and_conquer(x,y,size):
    global turn
    if y==R and x==C: print(turn-1)
    # print(x,y,size,turn)
    if size==1:
        turn+=1
        return
    #4등분씩 방문. 기준은 맨 왼쪽 위
    else:    
        divide_and_conquer(x, y, size//2)
        divide_and_conquer(x+size//2, y,size//2)
        divide_and_conquer(x, y+size//2, size//2)
        divide_and_conquer(x+size//2,y+size//2, size//2)

divide_and_conquer(0, 0, 2**N)

수정코드 (최적화 코드)

import sys
input=sys.stdin.readline

N,R,C=map(int,input().split())
turn=0
def divide_and_conquer(x,y,size):
    global turn
    if y==R and x==C: 
        print(turn)
        exit()
    # print(x,y,size,turn)
    if size==1:
        turn+=1
        return

    if not (y<=R<y+size and x<=C<x+size):
        turn+=size*size
        return
    #4등분씩 방문. 기준은 맨 왼쪽 위
    else:    
        divide_and_conquer(x, y, size//2)
        divide_and_conquer(x+size//2, y,size//2)
        divide_and_conquer(x, y+size//2, size//2)
        divide_and_conquer(x+size//2,y+size//2, size//2)

divide_and_conquer(0, 0, 2**N)

그냥 브루트포스로 구현하면 시간초과가 난다. 이유는 최적화를 한 번 더 할 수 있기 때문인데! 아래 코드에서 보면

if not (y<=R<y+size and x<=C<x+size):
        turn+=size*size
        return

우리는 결국 R행 C열 이 부분'만' 찾으면 사실상 끝나는 거라 굳이 R이 다른 칸에 있을 때에는 그 루프를 다 돌 필요 없이 그냥 size만큼 껑충 뛰어주면 좀 더 빠르게 끝난다.

 

---

3. 한 번에 풀었는가? X

최적화 부분을 놓쳐 한 번에 못 풀었다ㅠㅠㅠ