[BOJ] 1074 Z - JAVA

1. 문제

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

1074번: Z

---

2. 풀이

재귀함수를 이용한다.

0. n==0이라면 2의 0제곱, 즉 1이므로 함수를 종료한다.

1. r,c가 둘 다 절반보다 크다면 점이 4구역에 있는 경우이므로 나머지 세 면적을 더하고 4구역을 호출한다.

2. r만 절반보다 크다면 3구역에 있는 경우이므로 나머지 두 면적을 더하고 3구역을 호출한다.

3. c만 절반보다 크다면 2구역에 있는 경우이므로 나머지 한 면적을 더하고 2구역을 호출한다.

4. 위의 경우가 모두 아니라면 1구역을 호출한다.

import java.io.*;
import java.util.*;

public class BOJ_1074_Z {
    static int count,N,r,c;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());

        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        findRC(0,0,N);

        System.out.println(count);
    }

    private static void findRC(int y, int x, int n){
        if(n==0) return;

        int halfN = 1<<(n-1);
        int halfArea = halfN*halfN;//Math.pow(halfN,2);

        if(r>=y+halfN && c>=x+halfN) {
            count+=halfArea*3;
            findRC(y+halfN,x+halfN,n-1);
        }
        else if(r>=y+halfN){
            count+=halfArea*2;
            findRC(y+halfN,x,n-1);
        }
        else if(c>=x+halfN){
            count+=halfArea;
            findRC(y,x+halfN,n-1);
        }else{
            findRC(y,x,n-1);
        }

    }
}

---

3. 결과

아래 코드는 기저조건을 n==1로 놓고 그 안에서 델타값을 이용해 반복문을 돌린 코드다.

굳이 그렇게 할 필요 없이 n==0일 때 리턴만 해도 맞는 값이 나온다.