[코딩테스트/백준 알고리즘] 1074번 - Z (Java, 자바 풀이)

문제

https://www.acmicpc.net/problem/1074

1074번: Z

---

문제 설명

---

문제 풀이

맵을 사등분해서 좌표가 4개의 구역 중 어디에 위치하는지 추적한다.

한 구역에 든 요소의 수는 2²ⁿ⁻²이기 때문에 i번째 구역으로 이동하게 된다면 i * 2²ⁿ⁻²만큼의 카운트를 더해줘야 한다.

이 과정을 맵의 크기가 2X2 사이즈가 될때까지 반복하여 실행한다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int r = sc.nextInt();
        int c = sc.nextInt();
	
    	// 출력
        System.out.println(search(N , r, c));
    }


    static int search(int N, int r, int c) {
        int result = 0;
        int length = (int)Math.pow(2, N);

        if(N == 1) {
            if(r == 0 && c == 0)
                return 0;
            else if ( r == 0 && c == 1)
                return 1;
            else if (r == 1 && c == 0)
                return 2;
            else if (r == 1 && c == 1) {
                return 3;
            }
            return result;
        }
        else {
            if(r < length / 2 && c < length / 2) {
                result += search(N -1, r, c);
            }
            else if(r < length / 2 && c >= length / 2) {
                result += (long)Math.pow(2, 2 * N - 2);
                result += search(N - 1, r, c - (length / 2));
            }
            else if(r >= length / 2 && c < length / 2) {
                result += (long)Math.pow(2,  2 * N - 2) * 2;
                result += search(N - 1, r - (length / 2), c);
            }
            else if(r >= length / 2 && c >= length / 2) {
                result += (long)Math.pow(2, 2 * N - 2) * 3;
                result += search(N - 1, r - (length / 2), c - (length / 2));
            }
            return result;
        }
    }
}