[백준] 1074 Z / 자바(Java)

문제

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

1074번: Z

 

---

해설

Z형태가 반복되는 형상에 재귀 및 분할정복이 필요하다 생각들었습니다.

 

findz 함수를 통해 각 단계별로 r,c가 어느 사분면에 존재하는지를 구하고 그 단계의 사각형의 크기를 통해 그 사분면의 첫 숫자의 크기만큼 더해주어 마지막으로 사각형의 크기가 1인 경우에는 해당 사각형의 탐색 순서를 구할 수 있도록 하였습니다.

주의점

• 각 사분면단위로 계산하기 때문에 범위를 잘 판단해야한다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//	11524kb	76ms
public class Main{
	static int ans = 0;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		
		findZ(exp(2,N),r,c);
		
	}
	
	public static void findZ(int N, int r, int c) {
		int halfN = N/2;
		if(N==1) {
			System.out.println(ans);
			return;
		}
		// 1사분면
		if(0<=r && r<halfN && 0<=c && c<halfN) {
			findZ(halfN,r,c);
        //2사분면
		}else if(0<=r && r<halfN && halfN<=c && c<N) {
			ans += halfN*halfN;
			findZ(halfN,r,c-halfN);
        //3사분면
		}else if(halfN<=r && r<N && 0<=c && c<halfN) {
			ans += 2*halfN*halfN;
			findZ(halfN,r-halfN,c);
        //4사분면
		}else if(halfN<=r && r<N && halfN<=c && c<N) {
			ans += 3*halfN*halfN;
			findZ(halfN,r-halfN,c-halfN);
			
		}
		
	}
	public static int exp(int x,int n) {
		// 기저조건
		if(n==1) return x; 
		
		// 재귀로 구해옴( 둘로 나눌때 한번만 연산하기 위해)
		int y = exp(x,n/2); // 홀수건 짝수건 정수 /2 는 동일
		
		// 홀수 일때와 짝수일때 값을 보냄
		return (n%2==0)? y*y : y*y*x;
	}
	
}