[Java] BOJ 1074 Z

문제 

문제 링크 https://www.acmicpc.net/problem/1074

• 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

  

• N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
• 다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

  

• N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
• 다음은 N=3일 때의 예이다.

  

• 첫째 줄에 정수 N, r, c가 주어진다.
• r행 c열을 몇 번째로 방문했는지 출력한다.

아이디어

• 배열을 4등분하여 1,2,3,4분면으로 나눈 후, 구해야되는 열과 행을 기준으로 4등분한 부분의 어느 부분에 해당하는지 확인한다.
• 그리고 해당되는 사분면의 시작점의 숫자를 계산해서 저장한다.
• 시작점의 숫자는 크기를 곱한 값에 해당 사분면에 해당하는 0 ~ 3까지의 값을 곱한다.

겪은 시행착오

• 처음에는 배열을 선언해서 숫자의 규칙성을 찾아서 해당 행과 열의 숫자만 계산해서 저장할 생각이였지만 생각처럼 잘 되지 않아서 분할정복으로 풀었다...
• 사실 메모리 초과로 한번 틀렸는데... 위의 방법으로 풀려고 배열 선언해놓은 것을 안지워서 메모리 초과가 난 것이였다.... (배열을 생성한 것만으로 메모리 초과라니.. ㅜㅜ)

메모리 초과를 조심하자...!!

코드

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

public class BOJ1074 {
    public static void main(String[] args) throws Exception{
        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());

        // 2의 N제곱 구하기
        int num = (int)Math.pow(2, N);
        // 결과값
        int result = 0;

        // 크기가 1보다 크면 계속 반복
        while(num > 1){
            // 크기를 2로 계속 나눔 (사분면으로 분할하기 위해서)
            num = num / 2;

            // 행과 열이 2로 나눈 사이즈 숫자보다 작다면
            // 2사분면에 있다는 뜻
            if(r < num && c < num){
                // 결과값에 시작점의 숫자를 더함
                result = result + num * num * 0;
            }
            // 행이 사이즈보다 작고 열이 사이즈보다 크다면
            // 1사분면에 있다는 뜻
            else if(r < num && c >= num){
                result = result + num * num * 1;

                // 열의 크기를 현재 사이즈크기만큼 빼줌
                // 다시한번 작게 사분면을 나눠서 구분해야되므로
                c = c - num;
            }
            // 행이 사이즈보다 크고 열이 사이즈보다 작다면
            // 3사분면에 있다는 뜻
            else if(r >= num && c < num){
                result = result + num * num * 2;

                // 행의 크기를 현재 사이즈크기만큼 빼줌
                r = r - num;
            }
            // 행과 열이 사이즈보다 모두 크다면
            // 4사분면에 있다는 뜻
            else{
                result = result + num * num * 3;

                // 행과 열의 크기를 현재 사이즈만큼 빼줌
                c = c - num;
                r = r - num;
            }
        }

        System.out.println(result);
    }
}