[백준] 1074번 Z

1074번 Z

문제

입력

첫째 줄에 정수 N, r, c가 주어진다.

3 7 7

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

63

설명

1. 하나씩 divide & conquer를 하면 시간초과...
2. 4개로 나누고 단위면적을 이용해서 문제풀이
3. r,c의 위치에 따라 단위면적을 더해주는 방식으로 count를 더해준다.

   소스코드

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.StringTokenizer;
   

public class Main{
private static int N, r, c;
private static int count = 0;

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());

    int n = (int)Math.pow(2, N);
    int x=0, y=0;
    while(n > 1) {
        n /= 2;
        // 1 왼쪽 위
        if(r < x+n && c < y+n) {

        }
        // 2 오른쪽 위
        else if(r < x+n && c >= y+n) {
            count += n * n * 1;
            y += n; //오른쪽 위로 위치 이동
        }
        // 3 왼쪽 아래
        else if(r>= x+n && c < y+n) {
            count += n * n * 2;
            x += n;
        }
        // 4 오른쪽 아래
        else {
            count += n * n * 3;
            x += n;
            y += n;
        }
    }

    System.out.println(count);
}

}