[백준/BOJ] 1074번 : Z (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

1074번: Z

---

- 문제 -

 

난이도 실버 1 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

알고리즘 분류가 재귀로 되어있긴 하지만, 원래 재귀로 가능한건 반복문으로 가능하고, 반복문으로 가능한건 재귀로도 가능하기 때문에 무조건적으로 재귀로 풀진 않아도 된다. 하지만 굳이 분류에 써둔걸 보면 재귀를 활용했으면 하는것 같으니 재귀로 풀어보겠다.

 

푸는 방법은 Z가 형성되는 기준은 4칸이다. 작게 4칸이든 크게 4칸이든. 사진을 잘 보면 

이렇게도 Z인 것이다. 그렇다면 Z기준으로 그려진 칸들을 보면 작든 크든 4개로 분류 할 수 있을 것이다. 위 사진을 4개로 분류 하면.

이렇게 나눌 수 있을 것이다. 그렇다면 여기서 4개의 박스의 시작 값을 보자. 0 16 32 48이다.먼가 있어보인다.

위 표는 8 * 8이고, 4 * 4를 보자.

이렇게 4개의 박스로 또 나눠보고, 각 박스의 시작 점을 보자. 0 4 8 12이다. 있어보이네?

4 * 4일 경우 저 값은

(4 / 2) * (4 / 2) * 0 = 0

(4 / 2) * (4 / 2) * 1 = 4

(4 / 2) * (4 / 2) * 2 = 8

(4 / 2) * (4 / 2) * 3 = 12

 

그렇다면 8 * 8을 보자.

(8 / 2) * (8 / 2) * 0 = 0

(8 / 2) * (8 / 2) * 1 = 16

(8 / 2) * (8 / 2) * 2 = 32

(8 / 2) * (8 / 2) * 3 = 48

 

패턴이 보였다. 이제 이걸로 멀 할거냐.

내가 구하고 싶은 좌표가 어느 범위에 속해있는지를 찿을 것이다.

 

예를 들어보자. 3 3 1를 보자.

N이 3이면 2의 3제곱이기때문에 8이다. 우리가 구하고 싶은 좌표는 (3, 1).

8 * 8의 중간 좌표는 (8 / 2), (8 / 2) 인 (4, 4)이다.

생각을 해보자. 0으로 시작하는 왼쪽 위는 중간값보다 x y 다 작으니 (-, -)로 표현하자.

오른쪽 위는 x보다 작고 y보다 커야하니 (-, +).

왼쪽 아래는 (+, -), 나머지는 (+, +)이다.

이제 좌표가 아니라 횡렬로 표기되기 때문에 좌표로 생각하면 복잡하고, 사분면으로 생각해도 다른 점이 있기때문에 마찬가지로 복잡하다. 하지만 그렇다고 횡렬로 생각하게되면 그것나름대로 복잡하니 익숙한 좌표로 하는데 필자도 이것땜에 한참을 풀면서 헤깔렸다.

 

3,1의 위치를 보자. 4,4보다 (-, -) 이니 왼쪽 위에 위치 할 것이다. 그럼 거기서 끝이 아니지. 다음범위를 보자.

왼쪽 위의 범위는 0~15가 될 것이고, 크기는 4의 제곱이다. 중간값은 (2, 2)가 된다. 3,1는 2,2, 보다 (+, -)이다. 그렇다면 왼쪽 아래에 위치한 것이다.

다음 크기는 2의 제곱이다. 중간 값은 이번엔 1,1이 아닌 (3, 1)이 된다. 이유는 표를 보면서 하면 알 수 있겠지만, 왼쪽 위로 가면 1,1. 오른쪽 위로 가면 1, (1 + 2). 왼쪽 아래로 가면 (1 + 2), 1. 오른쪽 아래로 가면 (1 + 2), (1 + 2)가 되는 것이다.

3, 1기준으로 또 보자. 우리가 구하고 싶은 위치랑 어떤가 같다. 그렇다면 3, 1 위치에 있는 값은 Z로 다 지나오고 마지막 칸이기 때문에 오른쪽 아래에 있는 값을 구한다. 오른쪽 아래에 있는 시작값은 11.

다음 확인하기 위해 칸의 크기인 2의 1을 나누면 1이 된다. 1 * 1은 그냥 한 칸이기 때문에 11을 리턴해준다.

 

얼추 이해 되었으면 좋겠다. 필자는 이해했다.

 

코드를 보면 더 이해 될 수도 있다. 코드를 보자.

---

-풀이-

 

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

public class Main {
	static int x = 0;
	static int y = 0;
	static int count = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int result = Z((int)Math.pow(2, N), r, c);
		System.out.println(result);
	}
	
	public static int Z(int n, int r, int c) {
		//리턴될때마다 칸을 줄여준다. 1이 될때까지
		n /= 2;
		//왼쪽 위에 위치할때
		if(r < x + n && c < y + n) {
			count += (n * n * 0);
		//오른쪽 위에 위치할때
		}else if(r < x + n && c >= y + n) {
			count += (n * n * 1);
			y += n;
		//왼쪽 아래에 위치할때
		}else if(c < y + n) {
			count += (n * n * 2);
			x += n;
		//오른쪽 아래에 위치할때
		}else {
			count += (n * n * 3);
			x += n;
			y += n;
		}
		if(n == 1) return count;
		return Z(n, r, c);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.