[Baekjoon] 1074. Z [S1]

📚 質問する
https://www.acmicpc.net/problem/1074
大きな矩形から小さな矩形まで繰り返し解決される分割征服問題.
入力されたnは正方形の1辺の長さではなく、2のn次方の長さであるため、関数に2 ** nの平方を加え、関数の入力nは正方形の辺の長さであると考えられる.

入力された座標を先に見つけるために、4つの区間に分けて、どの部分に属するかを探します.

入力した座標(y,x)を矩形の辺の長さの半分にします.各象限は、(0,0)、(0,1)、(1,0)、(1,1)で定義することができる.
上図では、(0,1)にあります.

象限が定義されている場合は、各象限の左上隅の頂点の値を検索します.
矩形の1/4あたりの大きさは、入力されたnを2で乗算することによって求めることができる.

(0,0)表示(n**2)/2
(0,1)表示(n**2)/2)
(1,0)は((n*2)/2)2
(1、1)は((n*2)/2)3

開始部分の値をそれぞれ加算して0として計算すれば再帰関数を呼び出し,上記の方法で同様に小矩形を解決することができる.
開始部の座標値を使用して、小さな長方形で新しい座標値を探します.
(y,x)-(先頭のy,先頭のx)
関数の戻り値に対して시작 부분의 값 + recur()を呼び出し、開始部分の値を加算します.
nが1の場合、0を戻して終了します.

📒 コード#コード#

def recur(n, y, x):
    if n == 1:  # 더 이상 쪼개지지 않을 때 0을 return
        return 0
    
    n //= 2     # 작은 정사각형의 변의 길이는 원래 사각형의 절반이다.
    # 4 구역 중 y, x의 어디에 위치하는지 i, j에 담아준다.
    i = y // n  
    j = x // n
    # 작은 사각형에서 시작부분의 값 + recur(작은사각형의 변의 길이, 새로운 좌표)
    return (n * n) * (2 * i + j) + recur(n, y - n * i, x - n * j)

n, r, c = map(int, input().split())
print(recur(2 ** n, r, c))

🔍 結果