[BOJ/백준] 1074 Z (S1)

문제

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

풀이

좌측의 그림은 8x8로 이를 4등분을 하면 우측의 그림이 된다. (row, column)의 좌표까지의 칸수를 계산하는 건데, 한 변은 2^N으로 정의한다. 예를 들어 r=4, c=3,N=3 일 때, 일단 한 변의 길이는 8이 되므로 cut(8, 4, 3)가 실행된다.

 

half는 4등분을 했을 때, 4등분 한 사각형의 한 변의 길이이다. 첫 번째로 쪼개졌기 때문에 한 변의 길이인 half = 4가 된다.

• 1 사분면의 시작 값인 0의 좌표 = (0, 0)
• 2 사분면의 시작 값인 16의 좌표 = (0, half)
• 3 사분면의 시작 값인 32의 좌표 = (half, 0)
• 4 사분면의 시작 값인 48의 좌표 = (half, half)

구하려는 좌표가 (4, 3) 이므로 37이 위치하는 곳은 3 사분면이다. 코드에서 해당 좌표가 만족되는 부분의 코드를 보면 else if (r < half+half && c < half) 로 위 좌표 내에 드는 경우 3 사분면에 좌표기 위치한다고 판단한다. 

이제는 3사분면을 기준으로 재귀를 돌려야 하기 때문에 cnt에 1사분면 + 2사분면의 칸수의 합을 누적 시키고 cut(half, r - half, c);를 하여 시작점을 1사분면 위치로 옮기면서 구해야 하는 위치의 좌표가 (0, 3)이 된다. 

 

이번에는 오른쪽의 4x4의 그림을 가지고 4등분을 한 후 좌표에 맞추어 진행하면 된다.

 

이후에 1x1이 되면 해당 칸이 구하려는 칸이기 때문에 size가 1이 되므로 누적된 cnt 값이 출력된다.

Code

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

public class Main {
    static int N, r, c, cnt;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        int n = (int)Math.pow(2, N);  // 한 변의 길이 2^N

        cut(n, r, c);
        bw.flush();
        bw.close();
    }

    /**
     * 4등분
     * 문제의 첫 번째 그림인 2^1 * 2^1을 연결해서 한 것이므로 끝까지 들어가야 됨.
     * 1 | 2
     * ------
     * 3 | 4
     */
    public static void cut(int size, int r, int c) throws IOException {
        if (size == 1) {
            bw.write(cnt + "");
            return;
        }
        int half = size / 2;  // 4등분 했을 때, 각 사분면의 한 변의 길이
        /**
         * 각 사분면의 첫 좌표
         * - 1사분면 = (0, 0)
         * - 2사분면 = (0, 0+half)
         * - 3사분면 = (0+half, 0)
         * - 4사분면 = (0+half, 0+half)
         * r과 c는 각 좌표에 +half 한 값보다 작아야 함.
         */
        if (r < half && c < half) {  // 1 사분면
            cnt += half * half * 0;
            cut(half, r, c);
        } else if (r < half && c < half+half) {  // 2사분면
            cnt += half * half * 1;  // 1사분면의 칸수의 합을 cnt에 더해주고,
            cut(half, r, c - half);  // 1사분면의 위치로 재귀하여 다시 진행 (cnt에 이미 이전의 수들은 누적했으므로 c-half을 함으로써 위치만? 이동하여 다시 진행)
        } else if (r < half+half && c < half) {  // 3사분면
            cnt += half * half * 2;  // 1사분면 + 2사분면의 칸수의 합을 cnt에 저장
            cut(half, r - half, c);  // 3사분면에서 이어서 진행하지만 r-half을 함으로써 1사분면의 위치에서 재귀 진행
        } else if (r < half+half && c < half+half) {  // 4사분면
            cnt += half * half * 3;  // 1사분면 + 2사분면 + 3사분면의 칸수의 합을 cnt에 저장
            cut(half, r - half, c - half);  // 4사분면에서 이어서 진행하겠지만 r-half, c-half으로 1사분면에서 재귀 진행
        }
    }
}