https://www.acmicpc.net/problem/1074
문제
풀이
N이 15까지 커질 수 있기 때문에 2^15 배열을 만드는 것은 시간초과가 발생할 수 있다
분할정복을 활용하는 문제이다
전체 사각형을 4개 사분면으로 나누어 `(r, c)`가 어느 사분면에 있는지 알아내는 것이 중요하다
N이 2라고 가정하면 (4 x 4 사각형) 아래 배열이 나올 것이다
사각형을 절반으로 나누어 사분면을 만든다고 하면 아래 그림처럼 될 것이다 (2 x 2 사각형 4개)
`half = 2`
주어진 `(r, c)` 가 어느 사분면에 속하는지 구해야 한다
1사분면: `r < half` 이고 `c < half`
2사분면: `r < half` 이고 `c >= half`
3사분면: `r >= half` 이고 `c < half`
4사분면: `r >= half` 이고 `c >= half`
만약 `(r, c)`가 1사분면에 있다면 이전 사분면을 하나도 건너뛰지 않았다
2사분면에 있다면 1사분면을 방문하고 온 것이다
따라서 결과값에 `half * half`(1사분면의 크기)를 더해줘야 한다
3, 4사분면도 똑같이 건너뛴 사분면을 더해주어야 한다
3사분면 -> `2 * (half * half)`
4사분면 -> `3 * (half * half)`
`(r, c)`가 어느 사분면인지 알았다면 또 그 사분면에서 몇 번째인지 다시 찾아야 한다
그래서 좌표를 그 사분면의 시작점 기준으로 바꿔줘야 한다
만약 2사분면이라면 재귀 호출에 `(r, c - half)`를 넘겨줘야 한다
이렇게 N이 0이 될 때까지 재귀호출을 하면서 누적된 값이 정답이다
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int count; // 방문 카운트
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
find(N, r, c);
System.out.println(count);
br.close();
}
// 분할 정복
static void find(int N, int r, int c) {
// N이 0이 되면 종료 (사각형이 더이상 안만들어짐)
if (N == 0) {
return;
}
// 주어진 N의 반을 구한다
int half = (int) Math.pow(2, N - 1);
int square = half * half; // 반으로 나눈 사각형의 넓이
// 1사분면(왼쪽 위)
if (r < half && c < half) {
find(N - 1, r, c);
}
// 2사분면(오른쪽 위)
else if (r < half && c >= half) {
count += square; // 1시분면 크기만큼 더함
find(N - 1, r, c - half); // 좌표 재조정
}
// 3사분면(왼쪽 아래)
else if (r >= half && c < half) {
count += 2 * square; // 1, 2사분면 크기만큼 더함
find(N - 1, r - half, c); // 좌표 재조정
}
// 4사분면(오른쪽 아래)
else {
count += 3 * square; // 1, 2, 3사분면 크기만큼 더함
find(N - 1, r - half, c - half); // 좌표 재조정
}
}
}결과
