백준_ Z (분할 정복)

알고리즘 종류: 분할 정복
혼자서 풀었는가?: O

샤워실 바닥 타월 깔기 문제를 푼 뒤라서 그렇게 어렵게 풀지는 않았다 처음에는 문제 그대로 재귀로 풀면서 배열을 만들고 거기에 값을 넣을 생각을 했으나, N이 15까지 커질 수 있어서 이렇게하면 시간초과가 뜬다고 한다 따라서 이 방법으로 풀었다

문제 풀이

0 | 1
_ _

2 | 3

각각의 사분면에 해당하는 숫자가 위와 같다고 하자 Z 모양으로 탐색하는건 0사분면(좀 웃기긴 한데 나중에 풀이에서 곱해지는 숫자가 0이라 그냥 이렇게 정했다) -> 1사분면 -> 2사분면 -> 3사분면 순으로 탐색하는 것이다 이걸 재귀 함수를 사용해서 구현할 수 있다 잘 모르겠으면 문제에 있는 그림을 보자 그림을 보면 느낌이옴 암튼그럼

그런데 아까 말했던 대로 여기서 직접 배열을 만들면 시간초과가 뜬다.. 그래서 나는 다음과 같이 함수를 구현하였다 divide 함수는 재귀를 통해 계속 깊이 들어가면서 주어진 (r, c)가 어디 사분면에 있는지 단계마다 매번 파악한다. 그리고 해당 단계마다 제일 왼쪽 위에 위치한 원소의 값을 구하고 rst에 누적합을 한 뒤 함수로 넘겨준다 정사각형의 한 변의 길이가 2가 된 경우 rst에 적장한 값을 더히 리턴한다

(r, c)가 몇 사분면에 위치해 있는지 구한다
해당 사분면의 가장 왼쪽 위에 있는 값의 원소를 rst += 값 한 뒤에 다음 재귀로 넘어간다

Base case: n=1이면, 즉 한 변의 길이가 2인 경우엔
(r, c)가 0사분면일 때 - 지금까지 누적했단 값 + 0을 리턴
(r, c)가 1사분면일 때 - 지금까지 누적했단 값 + 1을 리턴
(r, c)가 2사분면일 때 - 지금까지 누적했단 값 + 2을 리턴
(r, c)가 3사분면일 때 - 지금까지 누적했단 값 + 3을 리턴

왜 +0,1,2,3을 리턴하는지, 왜 가장 왼쪽 위의 값을 누적하는지는 문제에 딸린 그림을 보면 금방 이해222

import sys

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


def divide(n, x, y, rst):
    xm = (x+x+pow(2, n)-1) // 2
    ym = (y+y+pow(2, n)-1) // 2

    if (n == 1):
        if (xm >= r and ym >= c): return rst
        elif (xm >= r and ym < c): return rst+1
        elif (xm < r and ym >= c): return rst+2
        elif (xm < r and ym < c): return rst+3
    
    if (xm >= r and ym >= c): return divide(n-1, x, y, pow(pow(2, n-1), 2)*0 + rst)
    elif (xm >= r and ym < c): return divide(n-1, x, ym+1, pow(pow(2, n-1), 2)*1 + rst)
    elif (xm < r and ym >= c): return divide(n-1, xm+1, y, pow(pow(2, n-1), 2)*2 + rst)
    elif (xm < r and ym < c): return divide(n-1, xm+1, ym+1, pow(pow(2, n-1), 2)*3 + rst)

print(divide(n, 0, 0, 0))

주의할 것은 몇 사분면에 위치해있는지 볼 때, r의 좌표와 c의 좌표 즉 x좌표와 y좌표를 비교하는 기준값이 다르다는 것이다 (xm, ym같이 변수 두 개가 필요하다) 그리고 이 변수 두 개를 구하기 위해서는 정사각형 한 변의 길이와 가장 왼쪽 위에 있는 원소의 x, y 좌표값이 필요하다 한 변의 길이가 8일 때 (4, 0)이 어디있는지 구해보려고 하면 이해될 것이다

이 부분은 샤워실 바닥 까는 문제에서도 실수가 있었는데 여기서도 비슷한 실수를 해서 남긴다