[백준] 1074 - Z

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

1074번: Z

문제 한줄 이해

-2^N*2^N의 그래프에서 Z 모양을 그리면서 번호 매겨가기.

 

생각난 풀이

1번째 방법: 분할정복 아이디어를 가지고 접근했다. 재귀함수를 이용해 그래프를 N//2의 크기로 잘라가면서 번호를 매겨 보려했다.

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

graph = [[0 for i in range(2**(N))] for i in range(2**(N))]


def dfs(x,y,N):
    global cnt
    #2*2의 격자 모양에 다다르면 Z를 그리며 번호 매기기
    if N == 2:
        dx = [0,0,1,1]
        dy = [0,1,0,1]
        for i in range(4):
            graph[x+dx[i]][y+dy[i]] = cnt
            cnt +=1
    else:
    #Z모양의 순서를 지키키 위해
    	#왼쪽 위
        dfs(x,y,N//2)
    	#오른쪽 위
        dfs(x,y+N//2,N//2)
    	#왼쪽 아래
        dfs(x+N//2,y,N//2)
    	#오른쪽 아래
        dfs(x+N//2,y+N//2,N//2)
        
cnt = 0
dfs(0,0,2**(N))
print(graph[r][c])

호기롭게 채점을 해봤지만 시간초과가 발생했다.

그래서 문제 조건을 다시 봤더니 시간제한이 0.5초였고 N이 15까지의 범위라는 것을 놓쳤다.

(문제에서 제한 조건과 범위 잘 살피기...)

 

2번째 방법: 시간을 줄이는 방법으로 1사분면에 순서만 매겨놓고 주어진 좌표가 몇사분면에 위치하는지 체크한 뒤 1사분면에 순서를 조정해주면 된다 생각했지만 1사분면에 순서만 적는것도 결국 1번 풀이와 같은 풀이가 반복이 되고 주어지 좌표가 어느 위치에 있는지 파악하려면 for문을 4구역으로 나누어야 했다.

다른 방법이 떠오르지 않아 검색으로 아이디어를 얻었다. 주어진 좌표만 탐색을 하는 것은 동일했지만 순서의 규칙성을 이용해 값을 찾는 것이였다. 여기서 순서의 규칙성이란 N//2 잘려 나갈때 1,2,3,4분면의 맨왼쪽 위 좌표가 0,N//2,N//2*2,N//2*3의 값을 가지고 2*2일때는 Z를 그려나가면서 0,1,2,3을 더하면 주어진 좌표에 대해서만 재귀를 실행해 시간을 단축할 수 있다.

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

def dfs(x,y,N):
    global cnt
    # print(cnt)
    # 1사분면
    if x < N//2 and y<N//2:
        if N == 2:
            print(cnt)
            return
        # print("1사분면")
        dfs(x,y,N//2)
    # 2사분면
    elif x < N//2 and y>=N//2:
        if N == 2:
            print(cnt+1)
            return
        # print("2사분면")
        cnt = cnt + (N//2)*(N//2)*1
        dfs(x,y-N//2,N//2)
    # 3사분면
    elif x >= N//2 and y<N//2:
        if N == 2:
            print(cnt+2)
            return
        # print("3사분면")
        cnt = cnt + (N//2)*(N//2)*2

        dfs(x-N//2,y,N//2)
    # 4사분면
    elif x >=N//2 and y>=N//2:
        if N == 2:
            print(cnt+3)
            return
        # print("4사분면")
        cnt = cnt + (N//2)*(N//2)*3
        dfs(x-N//2,y-N//2,N//2)
    

cnt = 0
dfs(r,c,2**(N))