분류 전체보기
-
백준 1074 : Z백준 2023. 11. 3. 03:09
1. 문제 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 접근 완전 탐색 최악의 경우에 $2^{15} X 2^{15} = $약 $10$억 -> Time limit으로 사용 불가능 분할 정복 $N = K$ 정사각형은 $N = K - 1$ 정사각형 $4$개를 합친 모양 -> 큰 문제를 작은 문제로 분할 모든 노드의 자식 노드가 $4$개인 트리로 전환 가능 3. 문제 해결 $N = K$ 정사각형을 4개로 분할 $N = K -..