[Unsolved][JAVA] 백준 1074 Z

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

1074번: Z

 

1. 서론

 

시&발 단언컨대 이건 실1의 수준이 아니다... 골5? ㅎ... 여하튼 실버임을 용납할 수 없는 문제다.

이 문제는 사실 1년 전... C++로 재귀공부를 하려다가 개같이 털리고 며칠을 고민하다가 결국 던져버린 문제이다.

왜 던졌냐면 구글에서 다른 사람 풀이를 봐도 내 대가리로는 도저히 이걸 짜고 이해할 수 없다는 결론에 다달았기 때문이다.

하지만 늘 그렇듯 포기한 문제, 나의 약점은 다시 부메랑처럼 나에게로 돌아온다... 나는 이 문제를 풀어야만 하게 됐고, 이렇게 다시 만나서 또 개같이 털리고... 결국 남의 코드를 보게 되었다. 그 때나 지금이나 코드를 보면 이런 원리로 돌아가는구나 알게 되지만 근데 이걸 어떻게 생각해냈지? << 여기서 막혀버리고 마는 것이다. 왜냐면 지금 이 코드의 동작 원리를 깨달아도 다음에 비슷하지만 다른 문제를 만나게 되면 결국 스스로 풀이를 떠올릴 수 없기 때문에 상당히 좌절스럽다. 여기까지만 징징거리고 본론으로....

 

2. 문제 풀이

 

문제에 나온 것처럼 배열을 Z로 탐색한다. 근데 그냥 Z가 아니라 4개씩 Z를 그은 후 그 옆으로 이동했다가 내려갔다가 상당히 복잡하게 이동한다. 단번에 재귀 문제인 건 알게 되지만 문제는 어떻게, 언제 이동하게 코드를 짤 것이냐는 것이다.

 

나는 처음에 아주 골 때리는 방법을 생각했다. N x N의 배열이라고 치면 N - 1, N - 1부터 0, 0까지 역순으로 이동해서 중간에 r,c를 구하면 그 값을 return 하려고 했다. 코드를 나름 열심히 짰지만 배열은 내 마음대로 움직여주지 않았다. 결국 이 방법은 버리고 구글링을 시도했다.

 

그랬더니 대부분의 사람들의 풀이가 거의 흡사했다. 하지만 나는 베끼고 싶지는 않고 위의 방법을 포기하고 0, 0부터 밑으로 내려가는 방법을 시도했다. 근데 배열의 크기가 작을 때는 성공했지만 배열의 크기가 커지면 이상한 좌표로 탐색하게 되었다. 이 방법은 아마 처음부터 불가능했거나, 내가 제약조건을 제대로 주는 법을 몰라서 그런 걸 수도 있지만 난 결국 이 방법도 포기했다. 지금의 내 뇌로는 더 이상 어떻게 제약조건을 줘야 하는지 떠오르지 않았기 때문이다.

 

그래서 결국 다시 구글링을 해서 나온 수많은 코드 중 가장 이해하기 쉬워보이는 코드를 골라잡았다.

 

https://wiselog.tistory.com/133

[백준 1074] Z(Java)

 

정말 놀랐다... 너무 간결했으나 그 내용은 간결하지 않았다. 천재인가?

(늘 재귀 코드를 보면 놀라는게 너무 복잡한 내용을 짧게 짜서)

이 제약조건을,, 어떻게 생각한 걸까?

 

배열의 길이를 가지고 배열에 들어가 계속 분할해 배열을 쪼개 준다. 지금의 길이의 /2를 하면 4 분할이 되는데 그 범위 안에 r, c가 있는지 계속 탐색한다.

만약 탐색 중 r, c중에 /2한 크기와 같은 값이 있다면 그 반면에 좌표값이 있는 것이기 때문에 그에 따라 값을 계산해준다.

(근데 이 공식을 어떻게 도출했는지 아직 모르겠음. 아마 좌표판 보고 숫자 조합해보면서 이렇게 하면 그 분면, 그 좌표의 값이 나온다라고 계속해봐서 이 공식이 나온 거겠지...? 대단;)

그리고 배열이 계속 작은 값으로 분열되기 때문에 그 분열된 배열판에 맞춰서 r, c 좌표의 위치도 조정해준다.

(이것도 위의 cnt 계산과 같이 이해 못했다... 아마 시도해보다 위에 적은 것처럼 왜 저렇게 해줬는지는 알지만 이 공식 도출 자체는 나 스스로는 못할 것 같다...)

 

3. 코드 설명

 

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

public class Main {

	static int cnt = 0, size;

	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());
		
		size = (int) Math.pow(2, n);
		
		find(size, r, c);
		System.out.println(cnt);
	}
	
	public static void find(int size,int r, int c) {
		if(size == 1)
			return;
		
		if(r < size / 2 && c < size / 2) { //1분면
			find(size / 2, r, c);
		}
		else if(r < size / 2 && c >= size / 2) { //2분면
			cnt += size * size / 4;
			find(size / 2, r, c - size / 2);
		}
		else if(r >= size / 2 && c < size / 2) { //3분면
			cnt += (size * size / 4) * 2;
			find(size / 2, r - size / 2, c);
		}
		else { //4분면
			cnt += (size * size / 4) * 3;
			find(size / 2, r - size / 2, c - size / 2);
		}		
	}
}

 

위에서 말한 그대로... 이 코드가 어떤 방식으로 동작하는지는 알지만 어떻게 이 방식을 도출해냈는지는 모르기 때문에... 설명 불가.

그냥 배열의 r,c좌표가 나올 때까지 4 분할하고, r, c좌표가 있는 분할을 찾으면 cnt 값을 계산하는 것...이라고 이해하지만

왜 cnt의 값이 분할에 따라 저 공식의 계산법이 나온건지는 잘... 모르겠다. (저렇게 규칙을 세운게,,, 아니 찾은 게? 대단)

(괴롭다....)

 

솔직히 다시 풀라고 해도 난 못 풀어 그냥 날 죽여~~