백준 1074번 Z

백준 1074번: Z

아이디어

시간제한 단 0.5초, N이 15일 때 배열 사이즈 약 10억개. 그냥 탐색해서는 풀 수 없다. 입력받은 r, c를 기준으로, 함수에 어떤 arguments를 넣을지 결정한다.

row, col이 현재 탐색중인 위치이다. 전체 배열을 4등분하여 r, c 가 어느 조각에 속해있는지 찾아내고 row, col을 그 조각에 맞게 업데이트한다.

이 때 ans 또한 해당 조각에 맞는 값으로 업데이트한다.

코드

import sys
input = sys.stdin.readline
N, r, c = map(int, input().split())

def solve(row, col, N, ans):
    if row == r and col == c:
        print(ans)
    else:
        if r < row + 2**(N - 1) and c < col + 2**(N - 1):
            solve(row, col, N - 1, ans)

        elif r < row + 2**(N - 1) and c >= col + 2**(N - 1):
            solve(row, col + 2**(N - 1), N - 1, ans + 2**(2*N - 2))

        elif r >= row + 2**(N - 1) and c < col + 2**(N - 1):
            solve(row + 2**(N - 1), col, N - 1, ans + 2**(2*N - 2)*2)

        elif r >= row + 2**(N - 1) and c >= col + 2**(N - 1):
            solve(row + 2**(N - 1), col + 2**(N - 1), N - 1, ans + 2**(2*N - 2)*3)


solve(0, 0, N, 0)

여담

완전탐색 조지다가 시간초과 ㅎ