백준 S1 1074 Z

문제링크

1074번: Z

 

접근 방식

하나의 정사각형은 4개의 정삭가형으로 나눠진다.

 

나는 해당 부분을 11시, 1시, 7시, 5시로 나눴다.

 

나는 열을 x 행을 y라고 하고 문제를 푸는 편이다.

4개로 분활한 각각의 정사각형의 좌측 최상단의 y, x 의 값은 그림과 같다.

 

그러면 각각의 좌측 최 상단의 y, x는 뭘 참고해서 구할 수 있을까?

 

위 그림에서 한변의 길이는 4라고 할 수 있다.

그리고 좌표를 잘 보면 알 수 있겠지만 2 라는 숫자.. 4/2 임을 알 수 있다.

 

즉 한변의 길이를 알면 나눠진 정사각형의 좌측 최상단 y, x 값을 알 수 있다.

 

이제 문제 예시를 보자

37 를 구한다고 하면 입력은 

3 4 3 을 받을 것이다.

 

37은 어느 방향에 있는가? 7시 방향에 있다.

우리는 입력은 4, 3을 활용해서 7시 방향으로 진행하도록 해야 한다.

 

		//7시 방향
		if((r >= leftTopY + newLen) && (c < leftTopX + newLen) )  {
			sum += (tmp*2);
			recursion(newLen, leftTopX, leftTopY+newLen);
			return;
		}

leftTopY 는 0 , leftTopX 는 0 newLen은 4이다. newLen은 한변의 길이 8를 2로 나눈 값이다.

행이 4보다 크거나 같고

열이 4보다 작으면 7시 방향으로 가는 것이다.

7시 방향으로 가면 상단의 두 정사각형의 cell의 개수를 result에 더해준다.

 

 

다음은 1시 방향으로 이동한다.

1시 방향으로 가면 11시 방향에 있는 정사각형 cell의 개수를 더해준다.

다음은 또 1시 방향으로 이동한다.

36쪽에 cell은 1개 이므로 정답에 1을 더해준다.

끝! 왜 37은 안더해주냐면 0에서 1로 가는게 횟수 1을 세는 거니깐 그렇다.

 

---

정답코드

 

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

public class Main {

	static int n, r, c, sum;
	static int[][] arr;
	static StringBuilder sb;
	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()); // 열
		n = (int) Math.pow(2, n); // 한변의 길이
		sum = 0; // 정답
		// 재귀함수 호출
		recursion(n, 0, 0);
		System.out.println(sum);

	}
	

	/**
	 * @param len               한변의 길이
	 * @param leftTopX          제일 좌측 상단 x
	 * @param leftTopY          제일 좌측 상단 y
	 */
	public static void recursion(int len, int leftTopX, int leftTopY) {
		if(len == 1) {
			return;
		}
		
		// 새로운 한변의 길이는 파라미터로 받은 한변의 길이를 2로 나눈다.
		int newLen = len/2;
		int tmp = newLen*newLen;
		
		//11시 방향
		if((r < leftTopY + newLen) && (c < leftTopX + newLen ) )  {
			recursion(newLen, leftTopX, leftTopY);
			return;
		}
		
		//1시 방향
		if((r < leftTopY + newLen ) && (c >= leftTopX + newLen ) )  {
			sum += tmp;
			recursion(newLen, leftTopX+newLen, leftTopY);
			return;
		}
		
		//5시 방향
		if((r >= leftTopY + newLen) && (c >= leftTopX + newLen) )  {
			sum += tmp*3;
			recursion(newLen, leftTopX+newLen, leftTopY+newLen);
			return;
		}
		//7시 방향
		if((r >= leftTopY + newLen) && (c < leftTopX + newLen) )  {
			sum += (tmp*2);
			recursion(newLen, leftTopX, leftTopY+newLen);
			return;
		}
		
	}
}