백준 1074번 Z

1. 문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제 입력 1 복사

2 3 1

예제 출력 1 복사

11

예제 입력 2 복사

3 7 7

예제 출력 2 복사

63

예제 입력 3 복사

1 0 0

예제 출력 3 복사

0

 

 

2 - 1. 나의 풀이

어떻게 풀 지 감은 잡았는데

코드를 어떻게 써내려가야 할 지 막막했다.

 

2차원 배열을 1, 2, 3, 4 사분면으로 나누면서 범위를 좁혀가면 되겠다 했다.

0, 16, 32, 48 각 사분면의 첫번째 값을 활요해볼까 했는데 어려웠다.

 

그래서 정답을 봄

 

3 - 1. 풀이

한 변의 길이를 size (2^n)이라고 할 때

2차원 배열의 크기는 size * size 이다.

사분면으로 좁혀 들어갈 때 마다 1/4씩 2차원 배열의 크기가 줄어든다.

그리고 중요한건 사분면으로 좁혀 들어갈 때 r행 c열의 값이 상대 위치가 달라진다는 것이다.

 

만약 변의 길이가 2^3일 때

7행7열을 구하고자 한다고 하자

 

처음 사분면을 판단하고 좁혀들어갈 때

7행 7열이었던 인덱스는 크기가 1/4배 된 배열에서 3행 3열이 된다.

여기서 발견할 수 있는 상대 위치 규칙성은

1사분면은 그대로

2사분면은 열(c)가 size /2 만큼 줄어든다.

3사분면은 행(r)이 size /2 만큼 줄어든다.

4사분면은 행과 열이 size /2 만큼 줄어든다.

 

사분면으로 좁혀 들어갈 때 마다

그 사분면의 첫 인덱스(0행 0열)을 더하면 된다.

위 예시에서는 7행 7열은 4 사분면이므로 (size * size ) *3 /4, 64 * 3 / 4 = 48을 더한다.

이걸 반복하면 나중에는 2 * 2 배열 만큼 작아지게 되어 0, 1, 2, 3의 값을 더하고 size가 1이 돼, 끝난다.

3 - 2. 코드

package solvedac;

import java.util.Scanner;

public class ac1074 {
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //차수
        int r = sc.nextInt();
        int c = sc.nextInt();
        //r행 c열
        int size = (int) Math.pow(2, n); //변의 길이

        findZ(size, r, c);
        System.out.println(count);


    }
    //변의 길이는 1/2씩 줄어든다.
    /*
    * 1사분면 size 1/2배, r과 c도 그대로
    * 2사분면 size 1/2배, c가 size/2 만큼 상대위치 감소
    * 3사분면 size 1/2배, r이 size/2 만큼 상대위치 감소
    * 4사분면 size 1/2배, r과 c가 size/2 만큼 상대위치 감소
    * */
    public static void findZ(int size, int r, int c) {
        if(size ==1) return;
        int half = size / 2;
        if (r < half)
        {
            if(c <half) {
                findZ(size / 2, r, c);
            }
            else {
                count += (size * size / 4);
                findZ(half, r, c - half);
            }
        } else {
            if (c < half) {
                count += (size * size / 4) * 2;
                findZ(half, r-half, c);
            }
            else {
                count += (size * size / 4) * 3;
                findZ(half, r - size / 2, c - size / 2);
            }
        }
    }
}

 

 

4. 얻어갈 점

경험 부족이다. 

많은 문제를 풀어보자

내가 못 풀거같은 문제를 풀려고 노력합시당.