[Silver I] Z - 1074
์ฑ๋ฅ ์์ฝ
๋ฉ๋ชจ๋ฆฌ: 31256 KB, ์๊ฐ: 44 ms
๋ถ๋ฅ
๋ถํ ์ ๋ณต(divide_and_conquer), ์ฌ๊ท(recursion)
๋ฌธ์ ์ค๋ช
ํ์๋ ํฌ๊ธฐ๊ฐ 2N ร 2N์ธ 2์ฐจ์ ๋ฐฐ์ด์ Z๋ชจ์์ผ๋ก ํ์ํ๋ ค๊ณ ํ๋ค. ์๋ฅผ ๋ค์ด, 2ร2๋ฐฐ์ด์ ์ผ์ชฝ ์์นธ, ์ค๋ฅธ์ชฝ ์์นธ, ์ผ์ชฝ ์๋์นธ, ์ค๋ฅธ์ชฝ ์๋์นธ ์์๋๋ก ๋ฐฉ๋ฌธํ๋ฉด Z๋ชจ์์ด๋ค.
N > 1์ธ ๊ฒฝ์ฐ, ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ 2N-1 ร 2N-1๋ก 4๋ฑ๋ถ ํ ํ์ ์ฌ๊ท์ ์ผ๋ก ์์๋๋ก ๋ฐฉ๋ฌธํ๋ค.
๋ค์ ์๋ 22 ร 22 ํฌ๊ธฐ์ ๋ฐฐ์ด์ ๋ฐฉ๋ฌธํ ์์์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ค์์ N=3์ผ ๋์ ์์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์ ์ N, r, c๊ฐ ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
rํ c์ด์ ๋ช ๋ฒ์งธ๋ก ๋ฐฉ๋ฌธํ๋์ง ์ถ๋ ฅํ๋ค.
๐ก Solutions
๐ Z.py
Z, r, c = map(int,input().split())
N = 2**Z
def rangemaker(row, col, size):
rng_x = [row, row+size]
rng_y = [col, col+size]
return [rng_x, rng_y]
def check(target, *args):
x,y = target[0],target[1]
place = 0
for arg in args:
row, col = rangemaker(arg[0],arg[1],arg[2])
if x in range(*row) and y in range(*col):
return arg, place
place += 1
return None
numb = 0
def sol(target, row, col, size, depth):
global numb
if target == (row, col):
return
new_size = size//2
node1 = (row, col, new_size)
node2 = (row, col + new_size, new_size)
node3 = (row + new_size, col, new_size)
node4 = (row + new_size, col + new_size, new_size)
next, node = check(target, node1, node2, node3, node4)
if next[2] != 1 : # size ๊ฐ 1์ด ์๋ ๊ฒฝ์ฐ
numb += size**2 * node// 4
else :
numb += node
sol(target, *next, depth+1)
sol((r,c), 0, 0, N, 0)
print(numb)