92 삐약 : 백준 1074| Z [바킹독| 재귀 |JAVA]

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

 

package BKD_0x0B_Recursion;

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

public class BOJ_1074 {
    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());

        System.out.println(getZ(n,r,c));
    }

    static int getZ(int n, int r, int c){
        if(n==0) return 0;
        int half = 1<<(n-1);

        if(r<half && c<half) return getZ(n-1,r,c);
        if(r<half && c>=half) return half*half + getZ(n-1,r,c-half);
        if(r>=half && c<half) return 2* half*half +getZ(n-1,r-half,c);
        return 3 * half*half +getZ(n-1,r-half,c-half);
    }
}

 

---

 

풀이

 

 

#1. 함수 정의

int func(int n, int r, int c)

2^n x 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수

 

 

 

#2. Base Condition

n==0 -> return 0;

 

 

 

#3. Recursion

 

area 1    |   area2

area3    |   area4

int half == 2^n-1

(r,c) in area1 => return func(n-1,r,c)
(r,c) in area2 => return func(n-1, r,c-half)
(r,c) in area3 => return func(n-1, r-half, c)
return func(n-1, r-half, c-half)