백준 1074. 골드 Z

문제

첫째줄에 N, r, c가 주어질 때 r행 c열을 몇번째로 방문했는지 출력한다.

풀이

이 문제의 경우 결국 스스로 해결하지는 못했지만, 유튜브 강의와 해설을 보고 이해할 수 있었다.

 

- N = 1 x 4개 =>  N = 2를 만든다.

- N = 2 x 4개 =>  N = 3을 만든다.

관계를 본다면 N = 2를 해결하기 위해서는 4사분면으로 나누고 N = 1을 재귀적으로 호출하면 해결가능하다.

사분면으로 나누기 위해서 절반을 기준으로 둔다.

half = 2 ** (N-1)

 

 

그리고 half를 기준으로 대소 관계를 비교하여 사분면을 나눈다.

N = 2일 때 i, j는 (3,3) 이지만 N = 1을 호출할 때 i, j는 (0,0)이다.

만약 i, j가 half를 기준으로 넘어간다면, half를 자르면 된다.

 

 

# 사분면 나누기
half = 2 ** (N-1)

if i < half and j < half: # 1사분면
quad = 1
elif i < half and j >= half: # 2사분면
j -= half
quad = 2
elif i >= half and j < half: # 3사분면
i -= half
quad = 3
elif i >= half and j >= half: # 4사분면
i , j = i-half, j - half
quad = 4

 

분할 정복을 하기전에 사분면 전의 칸의 수를 저장할 q라는 변수도 따로 더해주어야한다.

 

q += half * half * (quad -1) # 분할 정복하기 전 해당 사분면 앞에 있는 칸의 수
    
return solution(i,j, N-1, q)

 

전체 코드

def solution(i, j, N, q):
    if N == 0:
        return q
    
    # 사분면 나누기
    half = 2 ** (N-1)

    if i < half and j < half: # 1사분면
        quad = 1
    elif i < half and j >= half: # 2사분면
        j -= half
        quad = 2
    elif i >= half and j < half: # 3사분면
        i -= half
        quad = 3
    elif i >= half and j >= half: # 4사분면
        i , j = i-half, j - half
        quad = 4

    q += half * half * (quad -1) # 분할 정복하기 전 해당 사분면 앞에 있는 칸의 수
    
    return solution(i,j, N-1, q)

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

 

정리

N x N 크기의 공간에서 특정 위치 (r, c)의 인덱스를 찾아햐 하는 게 포인트이다.

각 단계마다 크기가 반인 사분면으로 나누고 그 사분면에서는 (r, c)의 위치를 조정하여 다시 분하 정복해나가야한다. (분할 정복)

어려우니 많이 풀어보기