Z - 1074번
문제링크: Z1074
🤔접근 방법
문제를 어떻게 풀어야 될지 몰라서 문제의 알고리즘 분류를 보고 힌트를 얻어 분할정복 알고리즘을 찾아봤다. 처음에는 어떻게 적용할까 고민했다. 분할정복은 간단히 설명하면 탐색하고 싶은 구간을 일정 규칙에 의해 분할하고 더 이상 쪼갤 수 없다면 병합해주는 알고리즘이다. 이 문제는 분할정복이지만 내가 봤을 때는 병합보다는 분할에 초점을 두고 푸는게 이상적이라 생각한다.
분할만 생각하게 된 계기
- 4등분을 할 수 있다.
- 수많은 것 중 한 개를 선택한다 = 더 이상 쪼갤 수 없다.
🤗풀이 방법
- 시작 지점과 끝 지점과 사각형의 최대길이를 생성한다.
- 사분면으로 쪼개야 되기 때문에 while문 시작 시 최대길이를 2로 나누어준다.
- 각 사분면의 시작점과 끝점을 지정하고 찾고 싶은 지점이 포함되는지 확인한다.
- 포함이 안된다면 현재 그
사분면의 개수(최대길이 x 최대길이)를 정답에 더해준다. - 2~4번 과정을 최대길이가 0이 될 때까지 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, ROW, COLUMN, maxLength;
static int answer = 0;
static int[] nowStart = {0, 0};
static int[] nowEnd = {0, 0};
//포함되는지 확인하는 함수
private static boolean isContain(int[] quarter) {
int[] nowStart = {quarter[0], quarter[1]};
int[] nowEnd = {quarter[2], quarter[3]};
boolean isContainRow = nowStart[0] <= ROW && ROW <= nowEnd[0];
boolean isContainColumn = nowStart[1] <= COLUMN && COLUMN <= nowEnd[1];
if(isContainRow && isContainColumn) return true;
return false;
}
public static void main(String[] args) throws IOException {
//입력
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
ROW = Integer.parseInt(st.nextToken());
COLUMN = Integer.parseInt(st.nextToken());
//끝점 초기화
maxLength = (int) Math.pow(2, N);
nowEnd[0] = maxLength - 1;
nowEnd[1] = maxLength - 1;
while(maxLength >= 1) {
maxLength /= 2;
//4등분
int[] quarter1 = {nowStart[0], nowStart[1], nowEnd[0] - maxLength, nowEnd[1] - maxLength};
int[] quarter2 = {nowStart[0], nowStart[1] + maxLength, nowEnd[0] - maxLength, nowEnd[1]};
int[] quarter3 = {nowStart[0] + maxLength, nowStart[1], nowEnd[0], nowEnd[1] - maxLength};
int[] quarter4 = {nowStart[0] + maxLength, nowStart[1] + maxLength, nowEnd[0], nowEnd[1]};
int[][] quarter = {quarter1, quarter2, quarter3, quarter4};
//사분면 탐색 만약 포함되는 곳이 생긴다면 다시 그 부분에서 탐색시작
for(int i=0; i<4; i++) {
if(isContain(quarter[i])) {
nowStart[0] = quarter[i][0];
nowStart[1] = quarter[i][1];
nowEnd[0] = quarter[i][2];
nowEnd[1] = quarter[i][3];
break;
}
answer += maxLength * maxLength;
}
}
System.out.print(answer);
}
}