백준 1074 Z Java

 

정답률 42퍼센트의 분할정복문제 Z이다.

 

배열을 만들어서 재귀호출로 숫자를 일일이 셌더니 바로 메모리초과가 나왔고

배열을 안만들고 재귀호출로 숫자를 일일이 세서 r과 c가 되면 멈추도록 했더니 시간 초과가 나왔다.

 

재귀호출로 숫자를 세서 시간초과가 안나왔다는 사람들도 있지만

내가 짠 코드는 시간초과가 계속 나왔다..

 

쨋든 성공한 사람들의 코드를 보니

일일이 세지 않고 r과 c를 보고

영역을 찾아가는 식으로 짰다.

 

x와 y를 현재 위치라고 생각하고

계속 해서 r과 c를 비교하며 영역을 찾아간다.

2영역 인경우엔 2영역에서 또 4분할 하여 영역을 찾아가야 하므로

n+x 또는 n+y로 비교한다..

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int r = scan.nextInt();
        int c = scan.nextInt();
        n = (int)Math.pow(2, n);
        int x = 0;
        int y = 0;
        int ans = 0;
 
        while(n > 1) {
            n /= 2;
            // 1 왼쪽 위
            if(r < x+n && c < y+n) {
                //아무것도 추가하지 않는다.
            }
            // 2 오른쪽 위
            else if(r < x+n && c >= y+n) {
                ans += n * n * 1; //횟수 추가
                y += n; //오른쪽 위로 위치 이동
            }
            // 3 왼쪽 아래
            else if(r>= x+n && c < y+n) {
                ans += n * n * 2;
                x += n;
            }
            // 4 오른쪽 아래
            else {
                ans += n * n * 3;
                x += n;
                y += n;
            }
        }
        System.out.println(ans);
    }