[백준] 1074번 - Z [Java]

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

 

[백준] 1074번 - Z [Java]

[백준] 1074번 - Z [Java]

[백준] 1074번 - Z [Java]

---

1.  아이디어

 

재귀 함수를 통해 r, c를 추적하며 찾아가면 해결할 수 있다.

---

2. 문제풀이

 

시간 제한이 0.5초여서 0부터 1씩 더하며 찾는건 시간 초과가 발생하고 배열로 처리하기에는 메모리 초과가 발생했다. 이를 해결하기 위해 재귀 함수를 통해 현재 바라보는 좌표가 r, c가 될 때까지 2차원 배열을 4분할해서 추적하며 찾아가는 방식으로 구현했다.

재귀 과정에서 현재 바라보는 좌표에 들어갈 값을 파라미터로 들고 다니며 도착 시 출력하는 방식으로 구현했고 현재 좌표에 들어갈 값은 4분할한 사각형의 어디 들어갈지에 따라 해당 사각형의 크기를 더하는 방식으로 구할 수 있다.

---

3. 코드

 

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

public class Main {

    private static int r;
    private static int c;

    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());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        int len = (int) Math.pow(2, N);
        long size = (long) len * len;

        recur(0, 0, len, len, 0, size);
    }

    private static void recur(int r1, int c1, int r2, int c2, long ans, long size) {
        if (r1 == r && c1 == c) {
            System.out.println(ans);
            return;
        }

        int midR = (r1 + r2) / 2;
        int midC = (c1 + c2) / 2;

        if (r < midR) {
            if (c < midC) recur(r1, c1, midR, midC, ans, size / 4);
            else recur(r1, midC, midR, c2, ans + size / 4, size / 4);
        } else {
            if (c < midC) recur(midR, c1, r2, midC, ans + size / 4 * 2, size / 4);
            else recur(midR, midC, r2, c2, ans + size / 4 * 3, size / 4);
        }
    }

}

---

4. 후기