[Java Algorithm] Z BOJ #1074

문제

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

1074번: Z

 

내 문제 풀이

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

public class BOJ_1074 {
	
	static int n, r, c, cnt;
	
	public static void move(int len, int r, int c) {
		if(len == 1) return; // 우리가 찾던 딱 한 칸만 남을 때 반환
		
		len /= 2; // 4등분한 한 변의 길이
		if(r < len && c < len) { // 1
			move(len, r, c);
		} else if(r < len && c < len*2) { // 2
			cnt += len*len;
			move(len, r, c-len);
		} else if(r < len*2 && c < len) { // 3
			cnt += len*len*2;
			move(len, r-len, c);
		} else if(r < len*2 && c < len*2) { // 4
			cnt += len*len*3;
			move(len, r-len, c-len);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		
		move((int)Math.pow(2, n), r, c);
		System.out.println(cnt);
	}

}

👉 분할 정복, 재귀 문제

 

✔️ 이 문제는,, 지문에,, 답이 있다,,!!

지문에서 말하는 그대로, 한 변이 2^N인 2차원 배열을 크게 4등분으로 나누고,

할 수 있는 방문 체크를 해 준 뒤, 그 다음엔 더 작은 범위의 배열을 4등분으로 나누고,, 방문체크,, 나누고,,

를 반복하는 재귀를 만들어주면 된다.

 

✔️ 우선 처음 주어진 r, c 자리가 배열을 4등분 했을 때 어디에 위치하는지 확인했다.
Z 모양으로 방문하기 때문에, 내가 속한 등분보다 왼쪽 혹은 위쪽에 위치하는 곳에 대해서는
굳이 전부 탐색할 필요가 없고, 그냥 해당 등분 칸 개수를 모두 더해주면 된다.

 

✔️ 위와 같은 방식으로, r, c를 좌측 상단으로 점점 옮겨가면서

배열의 범위를 점차 줄여가는 로직으로 재귀를 작성했다.

 

💡 피드백

• 꽤나 빡센 재귀문제였다. 재귀는 언제나 어렵따 !