백준 1074번
https://www.acmicpc.net/problem/1074
한수는 크기가 2 × 2인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2 × 2로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 × 크기의 배열을 방문한 순서이다.
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
를 통해 해당 좌표의 값을 파악하면
사이즈를 줄여가면서 원하는 값을 찾을 수 있다.
생각해보면 보통 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; } } } }