자바(백준) 1074 Z

오답 노트 & 새로 알게 된 점

처음에 완전탐색을 생각했다.

그러나 N이 최대 15로 2^15 * 2^15 = 2^30으로 완탐하면 무조건 TLE가 난다.

 

시간 복잡도를 줄일 방법이 없을까 생각을 했다.

크기가 2*2만큼 커지기 때문에 2*2를 재귀를 이용하여 줄이면서 짜면 될 것 같았다.

 

문제를 풀면서 생각해야할 점은 두가지이다.

 

1. 어느 사분면에 속해있는가

2. 2*2만큼 크기를 줄일 때, 좌표는 어떻게 변화되는가?

 

1번을 알아야하는 이유는 사분면마다 방문횟수를 더해주는 값이 다르기 때문이다.

1번 해결방법은 문제에서 찾을 수 있었다.

r과 c가 0부터 시작한다고 했다. 

즉, 주어진 한 변의 길이를(2^N)  절반으로 나눴을 때 왼쪽, 오른쪽에 있는지 구분만 하면 된다.

N = 4이면 0, 1은 왼쪽, 2,3은 오른쪽에 있듯이 말이다.

 

2번은 크기를 줄이면서 좌표는 어떻게 변화되는가이다.

1번과 연관이 있다.

1사분면은 좌표가 그대로, 2사분면은 row 그대로, col 변화

3사분면은 row 변화, col 그대로, 4사분면은 row, col 모두 바뀐다.

 

대표적으로 N = 3일 때, (2, 4), (2, 5),  (2, 6),  (2, 7)

은 (2, 0), (2, 1), (2, 2), (2, 3) 으로 바뀐다.

즉, col - len / 2라는 것을 알 수 있다.

 

아래의 그림을 보면 이해가 될 것이다.

 

---

코드

 

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, row, col;
    static int ans;
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        z(row, col, (int) Math.pow(2, N));
 
        System.out.println(ans);
    }
 
    static void z(int row, int col, int len) {
        if(len == 1) return;
 
        if(row < len / 2 && col < len / 2){
            z(row, col, len / 2);
        }
        else if (row < len / 2 && col >= len / 2) {
            ans += (len * len / 4);
            z(row, col - len / 2, len / 2);
        }
        else if(row >= len / 2 && col < len / 2){
            ans += (len * len / 4) * 2;
            z(row - len / 2, col, len / 2);
        }
        else{
            ans += (len * len / 4) * 3;
            z(row - len / 2, col - len / 2, len / 2);
        }
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
    }
}