백준#1074 Z (제일 어렵😭)

문제

https://www.acmicpc.net/problem/1074

풀이

나의 풀이

재귀함수에 대한 응용이 더 필요한 것 같다ㅠ.ㅠ

N, r, c = [int(x) for x in input().split()]


def get_quater(N, r, c):
    if r >= 2**(N-1) and c >= 2**(N-1):
        return 3
    if r >= 2**(N-1):
        return 2
    if c >= 2**(N-1):
        return 1
    return 0


def get_prev_items_count(N, q_index):
    return 2**(N-1) * 2**(N-1) * q_index


def foo(N, r, c):
    if N == 0:
        return 0
    q_index = get_quater(N, r, c)
    prev_items_count = get_prev_items_count(N, q_index)
    new_n = N-1
    new_r = r % 2**new_n
    new_c = c % 2**new_n

    return prev_items_count + foo(new_n, new_r, new_c)


print(foo(N, r, c))

쌤's 풀이 1

• 재귀함수의 특징과 구조화를 사용하는 것이 포인트!
  

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

# N : 0.0을 기준으로 x,y의 숫자

def Z(sz, x, y):
    if sz == 1:
        return 0

    # 한 맥시멈 셀의 크기//2
    sz //= 2

    # 미니멈 셀의 크기는 2*2
    for i in range(2):
        for j in range(2):
            if x < sz*(i+1) and y < sz*(j+1):
                # print('haha', (i*2+j) * sz*sz)
                return (i*2+j) * sz*sz + Z(sz, x-sz*i, y-sz*j)

print(Z(2**N, r, c))

남의 풀이 2

def solve(n, x, y):
    global result
    if n == 2:
        if x == X and y == Y:
            print(result)
            return
        result += 1
        if x == X and y + 1 == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y == Y:
            print(result)
            return
        result += 1
        if x + 1 == X and y + 1 == Y:
            print(result)
            return
        result += 1
        return
    solve(n / 2, x, y)
    solve(n / 2, x, y + n / 2)
    solve(n / 2, x + n / 2, y)
    solve(n / 2, x + n / 2, y + n / 2)


result = 0
N, X, Y = map(int, input().split(' '))
solve(2**N, 0, 0)