kingsubin

import java.io.*;
import java.util.*;
 
public class boj_1074 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, r, c;
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
 
        int ans = func(n, r, c);
        System.out.println(ans);
    }
 
    static int func(int n, int r, int c) {
        if (n == 0) return 0;
        int half = (int) Math.pow(2, n-1);
 
        // 1번 사각형
        if (r < half && c < half) {
            return func(n-1, r, c);
        }
        // 2번 사각형
        if (r < half && c >= half) {
            return half*half + func(n-1, r, c-half);
        }
        // 3번 사각형
        if (r >= half && c < half) {
            return 2*half*half + func(n-1, r-half, c);
        }
        // 4번 사각형
        return 3*half*half + func(n-1, r-half, c-half);
    }
}
 

 

- 재귀 -> 귀납적으로 생각

- 크기가 n인 배열의 (r, c) 는 크기가 n-1인 배열의 (r, c) 를 통해 구할 수 있다.

 

1. 함수의 정의

-> 2^n * 2^n 배열에서 (r, c) 를 방문하는 순서를 리턴하는 함수

 

2. base condition

-> n = 0 일때 return 0;

 

3. 재귀 식

-> 전체를 4등분하면 결국엔 사각형이 4개가 됨

1번 2번 3번 4번으로 번호를 붙였다고 생각

 

r,c 의 위치가 1번, 2번, 3번, 4번 사각형일 경우로 나누어서 생각

 

 

    

---

www.acmicpc.net/problem/1074