백준 1074번
https://www.acmicpc.net/problem/1074

문제

한수는 크기가 2$^N$

N > 1인 경우, 배열을 크기가 2$^N-1$

다음 예는 $2^2$ × $2^2$ 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

생각하기

우리가 만들어서 찾을 모양 자체가 정사각형이라는 점을 이용하면 된다
또한, 2 x 2 사이즈 반복이라고 생각하면서 줄여나가면 된다.

동작

먼저 한면의 사이즈 size값을 파악한다.
어차피 정사각형이기 때문에 한면의 값만 파악해도 충분

이 값을 이용해서 4등분해서 다시 작은 정사각형으로 만든다.
이 size값을 /2 하면 위 아래 4등분 한 값을 추정할 수 있다.

우리가 찾는 위치 r, c가 어느 분면에 위치해 있는지 파악한다.

만약 찾는 위치의 좌표값(r,c) 보다 사이즈의 시작점인x+size, y+size가 클 경우
우리가 찾는 위치가 앞쪽에 위치해 있다는 것을 의미한다.

이렇게 각 조건에 맞춰서 size를 통해 해당 좌표의 값을 파악하면

사이즈를 줄여가면서 원하는 값을 찾을 수 있다.

TMI

생각해보면 보통 2차원 배열 생성할 때도 z형태 순서로 생성되는데
왜 그 점을 생각하지 못했을까

코드

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

public class Main {
	static int size = 1;
	static int N, r, c;

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

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

		int count = 0;
		int x = 0;
		int y = 0;

		while(size > 0) {
			size /= 2;			
			if(r < x+size && c < y+size) {
				count += 0;
			}
			else if(r < x+size) {
				count += size * size;
				y += size;
			}
            else if (c < y+size) {
                count += size * size * 2;
                x += size;
            }
            else {
                count += size * size * 3;
                x += size;
                y += size;
            }
	

			 // size가 1이 되면 종료.
			 if(size == 1) {
	                System.out.println(count);
	                break;
	         }
		}

	}

}