BOJ#1074 Z

BOJ#1074 Z

* 문제

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

* 풀이

- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다.

 1. 문제를 더 작은 문제로 분할하는 과정(divide)

 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

(출처 : 알고리즘 문제 해결 전략)

위 해결 전략을 염두하고 알고리즘을 구상해봅시다.

1. 나눌 수 있는 경우 (divide & merge)

(r, c)가 몇 사분면에 있는지 알아냅니다

만약 3 사분면이라면

1, 2 사분면의 사각형의 개수는 쉽게 구할 수 있을 것입니다.

2. 나눌 수 없는 경우 (base case)

(r, c) 위치의 탐색 순서를 반환합니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%231074/src/Main.java

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

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 unitSize = (int) Math.pow(2, N - 1);

        System.out.println(solve(unitSize, r, c));
    }

    static int solve(int size, int r, int c) {

        // Base Case (더이상 나눌 수 없는 경우)
        if (size <= 1) {

            return (r * 2) + c;
        }
        // 나눌 수 있는 경우
        else {

            // divide & merge
            // 위치 확인

            return ((r / size) * 2 * size * size) + ((c / size) * size * size) + solve(size / 2, r % size, c % size);
        }
    }
}