백준 1074번 : Z(Java)

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

1074번: Z

---

[풀이]

 

- 재귀 유형의 문제입니다.
- 다음 칸을 방문하는 규칙은 일정하게 z 모양을 유지합니다.
- 또한 배열의 크기는 2의 배수로 일정합니다.
- 그러므로 재귀적으로 문제를 해결해야 합니다.
- 재귀적으로 문제를 해결하기 위해 전체 배열을 1,2,3,4 이렇게 사분면을 나누어 생각해야 합니다.(실제 수학의 사분면과는 다른 개념입니다. z모양에 따른 사분면입니다.)
- 1사분면일 경우에는 count 전역 변수는 그대로, 2사분면일 경우에는 1사분면의 방문횟수를 더하고, 3사분면일 경우에는 2사분면까지의 방문횟수를 더해야 합니다.
  - 이때, 각 사분면에 숫자가 없는 경우는 없으므로 사이즈(변의 길이)를 이용해서 계산합니다.
- 다음 재귀에 대한 조건은 r행 ,c열에 대한 위치를 기반으로 구현해야 합니다.
  - ex) n = 3, r = 7, c = 3 -> 7행 3열일 경우 다음 재귀 메소드는 어디서 실행되는지 생각해보면 이해가 되실 겁니다.

 

---

[코드]

 

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

public class Main {
	static int n,r,c,count;
	
	public static void main(String[] args) throws IOException {
		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());
		double size = Math.pow(2,n);
		count = 0;
		solve(size,r,c);
		
		System.out.println(count);
	}
	
	public static void solve(double size, int r, int c){
		if(size == 1)
			return;
		
		if(r < size/2 && c < size/2){
			solve(size / 2,r,c);
		}else if(r < size / 2 && c >= size/2){
			count += Math.pow(size,2) / 4;
			solve(size / 2, r, c - (int)size / 2);
		}else if(r >= size / 2 && c < size / 2){
			count += Math.pow(size, 2) / 4 * 2;
			solve(size / 2, r - (int)size / 2, c);
		}else if( r >= size / 2 && c >= size / 2){
			count += Math.pow(size, 2) / 4 * 3;
			solve(size / 2, r - (int)size / 2, c - (int)size / 2);
		}
	}
}