[ 백준 - 1074 ] Z

 

[ 1074 - Z ]

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

 

[ 📌 서론 ]

내가 마지막에 이 문제를 풀었을 때에는 Silver 1 이었는데, 언제 난이도가 상승 했다.

나는 재귀 함수를 설계하는게 이상하게 어려워서 이런 문제로 연습을 많이 했는데, 오랜만에 다시 풀게 되었다.

예전 풀이와 비교 했을 때 더 좋아진걸 보니 성장 했음을 느낀다.

 

풀이 과정에서도 과거에 이 문제를 처음 접했을 때는 문제 접근이 막막 했었고, 풀이도 정말 오래 걸렸는데, 성장이 눈에 보이지는 않지만 아주 조오오오금 늘었다고 생각해도 되지 않을까..?

---

[ 📌 풀이 ]

다양한 풀이가 있겠지만 주어진 2차원 배열이 2^N * 2^N 사이즈를 유지하기 때문에 복잡한 계산 없이 풀 수 있고, 4 개의 사분면으로 나눠서 문제를 풀이 할 수 있다.

 

당연하게도 배열에 요소에 하나씩 번호를 매겨가면서 풀이 하면 시간 초과가 난다.(경험담)

[ 사분면으로 나눠서 보자 ]

 

각 사분면의 경계를 기준은 2^N / 2 의 값이 연관되어 있는데 좌표를 표기 한다면 아래와 같다.

[ 경계에 각 좌표 표시 ]

문제를 풀 때 주어진 좌표가 어느 사분면에 위치 하는지 확인하고 범위를 좁혀 가면서 최소 크기가 될 때 까지 재귀 함수를 호출하면 되는데, 이와 동시에 숫자 카운팅도 같이 되어야 한다.

카운팅

만약 주어진 좌표가 3 사분면에 속한다면

Z 가 그려지는 순서는 2 -> 1 -> 3 -> 4 분면 순서로 그려지기 때문에 1, 2 사분면에 속한 요소들의 합을 카운팅 하면서 재귀 함수를 호출 하면 된다.

---

[ 📌 코드 - Java ]

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

public class Main {

    public static int N;
    public static int r;
    public static int c;
    public static long ans = 0;

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

        N = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        search(0, 0);
    }

    // x, y 1 사분면의 시작 지점
    public static void search(int x, int y) {
        final int n = (int) Math.pow(2, N);  // 2^N
        final int t = n * 2;
        final int quadSize = n * n;  // 사분면에 속한 요소의 개수

        if(N-- >= 0) {
            if(x <= r && r < x + n && y <= c && c < y + n) {
                search(x, y);
            } else if(x <= r && r < x + n && y + n <= c && c < y + t) {
                ans += quadSize;
                search(x, y + n);
            } else if(x + n <= r && r < x + t && y <= c && c < y + n) {
                ans += (quadSize * 2);
                search(x + n, y);
            } else {
                ans += (quadSize * 3);
                search(x + n, y + n);
            }
            return;
        }

        System.out.println(ans);
    }
}

---

[ 📌 코드 - Python ]

아주 처음에 풀었던 파이썬 코드인데 이 때에는 재귀함수에 익숙하지 않아서 `가장 작은 단위` 까지 쪼개지 못해서 마지막에 가서 for 반복을 통해서 정리해 주었다....

 

java 코드와 비교 했을 때 로직이 하나 더 들어가 있는걸 확인할 수 있다.

가장 작은 단위인 4 개의 요소가 남았을 때 Z 를 그리면서 하나씩 카운팅 했는데, 이 부분을 보고 성장을 느꼈다.

import sys
N, r, c = map(int, sys.stdin.readline().split())
cnt = -1

def search(x, y, n):
  global r, c, cnt

  next_n = n // 2
  quad_cnt = pow(next_n, 2)

  if n != 2:
    if x <= r < x + next_n and y <= c < y + next_n:
      search(x, y, next_n)
    elif x <= r < x + next_n and next_n <= c:
      cnt += quad_cnt
      search(x, y + next_n, next_n)
    elif next_n <= r and y <= c < y + next_n:
      cnt += quad_cnt * 2
      search(x + next_n, y, next_n)
    else:
      cnt += quad_cnt * 3
      search(x + next_n, y + next_n, next_n)
    return

  for i in range(x, x + 2):
    for j in range(y, y + 2):
      cnt += 1
      if i == r and j == c:
        print(cnt)
        sys.exit()

search(0, 0, pow(2, N))