[백준] 1074번 Java (재귀, 분할정복)

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

💡문제

풀이

접근법 : 배열을 사분면으로 나눈다!
왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래가 재귀적으로 반복된다.
어느 사분면인지 파악 -> 계산 -> 1사분면으로 보내기 -> 1사분면을 또 사분면으로 나누기. 이걸 반복하여 배열의 한변의 크기가 1이 되면 r,c를 찾은 것이므로 반환한다.

• 2, 3, 4사분면에 있는 경우

  • 1사분면 만큼(size/2)을 제외하고, 2사분면부터 방문한 횟수를 계산해서 answer에 더해준다.

  • r,c의 위치에서 size/2(1사분면의 길이)만큼 빼서 1사분면 쪽으로 보내준다.

  • 다시 어느 사분면에 있는지 파악한다.
    
    

• 1사분면에 있는 경우

  • size/2인 배열로 잘라(즉, 다시 사분면으로 나누어) 다시 r,c의 위치를 찾는다.

내 코드

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

public class Main {
    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());
        int size = (int) Math.pow(2, n);    //배열의 한 변 크기
        int answer = funcZ(r, c, size, 0);  // 0부터 방문 횟수 계산
        System.out.println(answer);
    }

    public static int funcZ(int r, int c, int size, int answer) {
        // 배열의 한 변의 크기가 1이 되면 r,c를 찾은 것이므로 반환
        if (size == 1) {
            return answer;
        }
        
        int hSize = size / 2;	// 1사분면의 길이
        
        // 1사분면에 있는 경우
        if (r < hSize && c < hSize) {
            return funcZ(r, c, hSize, answer);

            // 2사분면에 있는 경우
        } else if (r < hSize && c >= hSize) {
            return funcZ(r, c - hSize, hSize, answer+ hSize * hSize);

            // 3사분면에 있는 경우
        } else if (r >= hSize && c < hSize) {
            return funcZ(r - hSize, c, hSize, answer + hSize * hSize * 2);

            // 4사분면에 있는 경우
        } else {
            return funcZ(r - hSize, c - hSize, hSize, answer + hSize * hSize * 3);
        }
    }
}