QA & Engineering Blog

A Blog about Quality ยท Automation ยท Engineering

๐Ÿ  ํ™ˆ์œผ๋กœ

[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)