[Java] Z [1074번]

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

• 예제 입력1

2 3 1

• 예제 출력1

11

• 예제 입력2

3 7 7

• 예제 출력2

63

• 예제 입력3

1 0 0

• 예제 출력3

0

• 예제 입력4

4 7 7

• 예제 출력4

63

• 예제 입력5

10 511 511

• 예제 출력5

262143

• 예제 입력6

10 512 512

• 예제 출력6

786432

---

• 문제 접근
  • N이 1인 경우에는 순서대로 0, 1, 2, 3을 출력하도록 설정
  • N이 2이상인 경우 2^(N-1)의 크기로 4등분을 한 후 재귀 함수
• 문제 해결
  • 하나 하나 순차적으로 진행을 하게 되면 N의 최대값이 15로 2^15으로 32,768 * 32,768의 길이가 되어 재귀 함수로 인한 Stack Overflow가 발생
  • 핵심은 구해야 할 row, col을 가지고 몇 사분면에 포함이 되는 지 확인
  • 사분면이 확인 되면 다시 사분면을 나누고 탐색하는 것을 반복하여 2x2의 크기까지 사분면을 나누고, 사분면 위치에 따른 값을 더해주는 것이 재귀 함수의 포인트
  • 사분면의 시작 값은 다음과 같다
    • 1사분면 시작값 ⇒ (2^N / 2) * (2^N / 2) * 0
    • 2사분면 시작값 ⇒ (2^N / 2) * (2^N / 2) * 1
    • 3사분면 시작값 ⇒ (2^N / 2) * (2^N / 2) * 3
    • 4사분면 시작값 ⇒ (2^N / 2) * (2^N / 2) * 4

• 슈도 코드

N(N 저장), targetRow(목표행 저장), targetCol(목표열 저장)
Z(N, targetRow, targetCol) 출력

Z(N, row, col){
	if(N이 1이라면){
		targetRow가 0이고 targetCol이 0이면 0 반환
		targetRow가 0이고 targetCol이 1이면 1 반환
		targetRow가 1이고 targetCol이 0이면 2 반환
		targetRow가 1이고 targetCol이 1이면 3 반환
	}
	size(2^(N-1) 저장)
	if(row가 size보다 작다면){
		if(col이 size보다 작다면){
			// 1사분면
			Z(N-1, row, col) 반환
		} else {
			// 2사분면
			Z(N-1, row, col - size) + size * size 반환
		}
	}else {
		if(col이 size보다 작다면){
			// 3사분면
			Z(N-1, row - size, col) + size * size * 2 반환
		}else {
			// 4 사분면
			Z(N-1, row - size, col - size) + size * size * 3 반환
	}
}

 

• 코딩하기

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] input = Arrays.stream((br.readLine()).split(" ")).mapToInt(Integer::parseInt).toArray();
    br.close();
    int N = input[0], targetRow = input[1], targetCol = input[2];
    System.out.println(Z(N, targetRow, targetCol));
}

private static int Z(int N, int row, int col){
    if(N == 1)
        return row == 0 ? col == 0 ? 0 : 1 : col == 0 ? 2 : 3;
    int size = (int)Math.pow(2, N-1); // 전체 길이의 절반으로 row, col을 확인하여 몇 사분면인지 확인
    if(row < size){ // 행이 절반 사이즈보다 작다면 -> 가운데 기준 윗쪽 -> 1, 2사분면
        if(col < size){ // 열이 절반 사이즈보다 작다면 -> 가운데 기준 왼쪽 -> 1사분면
            // 1사분면
            // 1사분면을 다시 사분면으로 나누기 위해 N - 1 전달
            return Z(N-1, row, col) + size * size * 0;
        }else { // 열이 절반 사이즈보다 크다면 -> 가운데 기준 오른쪽 -> 2사분면
            // 2사분면
            // N-1을 보내 사이즈가 1/2로 더 줄게 되면,
            // 현재 size보다 큰 col은 IndexOutOfBoundsException이 발생
            // 따라서, col에서 size만큼을 뺴주어야 함
            return Z(N-1, row, col - size) + size * size * 1;
        }
    }else {// 행이 절반 사이즈보다 크다면 -> 가운데 기준 아래쪽 -> 3, 4사분면
        if(col < size){ // 열이 절반 사이즈보다 작다면 -> 가운데 기준 왼쪽 -> 3사분면
            return Z(N-1, row - size, col) + size * size * 2;
        } else { // 열이 절반 사이즈보다 크다면 -> 가운데 기준 왼쪽 -> 4사분면
            return Z(N-1, row - size, col- size) + size * size * 3;
        }

    }
}