🧩 Problem Solving
[BOJ] 백준 1074번: Z
date
Sep 17, 2022
slug
boj-1074
author
status
Public
category
🧩 Problem Solving
tags
BOJ
summary
type
Post
thumbnail
문제링크
문제분석 및 설계
2차원 이분탐색 방식으로 재귀호출
주어진 배열에서 4개로 격자 나눈 후에
2 | 1
ㅡㅡㅡ
3 | 4
4개의 사분면 중 목표 인덱스가 어느 사분면인지에 따라 호출 위치 달라짐
- 2사분면이라면 count 그대로, 2사분면 재귀 호출
- 1사분면이라면 2사분면만큼 count 더하고 1사분면 재귀 호출
- 3사분면이라면 2, 1사분면만큼 count 더하고 3사분면 재귀 호출
- 4사분면이라면 2, 1, 3사분면만큼 count 더하고 4사분면 재귀호출
사이즈가 1이고 현재 인덱스가 목표 인덱스와 같다면 지금까지 더해온 count 출력
실패: 시간초과
모든 인덱스 위치를 방문하면 시간초과
4개의 사분면 중 목표 인덱스가 어느 사분면에 있는지 확인한 후 해당 격자만 재귀호출 해야 함