백준 1074번 : Z 자바

🧫 문제 분석

 

✔️ 출처

Z 실버 1

 

📖 문제

 

 

문제에서 답을 줬다.

 n-1 크기로 4등분

배열을 4 등분 하면서 구역을 4구역으로 나눈다. 

 

(r,c) 의 위치가 어느 구역인지 판별후 

해당 구역의 이전 구역들의 방문 수를 더하면서 

n == 1 일때가지 진행한다.

 

 

내가 짠 코드는 문제에서 n-1 크기로 줄여가며 4등분하는 것을 활용해서 했더니 

다른 사람들과 차이가 난다. 좀 복잡하게 풀었다.

 

 

 

---

🔅 문제 풀이

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

public class Main {

    static int[][] arr;
    static int r;
    static int c;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        recursion(N, 0, 0);

        bw.write(count + "\n");
        bw.flush();
        bw.close();
    }

    private static void recursion(int n, int yPow, int xPow) {

        // n-1 로 4등분할 기준 값
        int pow = (int) Math.pow(2, n - 1);

		// 마지막으로 2^n 이 1일 때 for문으로 순회하면서 count
        if (pow == 1) {
            for (int i = yPow; i <= yPow + 1; i++) {
                for (int j = xPow; j <= xPow + 1; j++) {
                    if (i == r && j == c) {
                        return;
                    }
                    count++;
                }
            }
        }

        int x = xPow + pow;
        int y = yPow + pow;

        int tmp = (int) Math.pow(pow, 2);
        
        if (y <= r) {
            // 4구역
            if (x <= c) {
                count += tmp * 3;
                recursion(n - 1, y, x);

                // 3구역
            } else {
                count += (tmp * 2);
                recursion(n - 1, y, xPow);
            }
        } else {
            // 2구역
            if (x <= c) {
                count += tmp;
                recursion(n - 1, yPow, x);
                
                // 1구역
            } else {
                recursion(n - 1, yPow, xPow);
            }
        }

    }

}

 

---

다른 사람 풀이

    private static void recursion(int n, int r, int c) {

        if (n == 1) {
            return;
        }

        int size = n / 2;

        // 1구역
        int newRow = r + size;
        int newCol = c + size;
        if (R < newRow && C < newCol) {
            recursion(size, r, c);

            // 2구역
        } else if (R < newRow && C >= newCol) {
            count += size * size;
            recursion(size, r, newCol);

            // 3구역
        } else if (R >= newRow && C < newCol) {
            count += size * size * 2;
            recursion(size, newRow, c);

            // 4구역
        } else if (R >= newRow && C >= newCol) {
            count += size * size * 3;
            recursion(size, newRow, newCol);
        }

    }

 

 

이해해보기

 

n은  2^N 이다.   초기 호출은 2^N, 0, 0

 

구역을 나눌때 

1 2

3 4 

라하자.

 

어짜피 4등분 되기에 한 쪽 면의 1/2을 얻고 이 값을 기준으로 4구역을 나눈다.

각 구역에서 n이 1이 될때까지 4등분해서 그 구역으로 재귀호출한다고 생각하면 된다. 

 

 

 

 

 

❗ 오답노트 / 필요한 지식

1. 비록 더 효율적인 코드가 있었지만 풀었음에 만족한다.
2. 다른사람의 코드를 보면서 내 코드를 더 발전시키자.