[Java] 백준 1074.Z

➡️문제 링크

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

 

💡아이디어

일단 무슨 말인지는 알겠는데 구현하려고 하니까 아이디어가 잘 떠오르지 않았다

DP? 그리디? 그래프탐색? 완-탐? 뭐지 하다

일단 DP라면 dp[i]에 뭘 저장할건데? 저장해서 다음값 쓸 때 어떻게 이용할 건데? 이 생각이 들어 패스

 

그러다 뭔가 쪼개고 쪼개서 구하는게 아닐까 싶었다.

문제를 다시 보면, 결국 지그재그 4set가 반복되는 거였고, 

그렇다면 현재 위치가 포함된 지그재그 set의

1. 첫 번째 원소값의 위치를 구하고

2. 해당 위치 전까지의 개수를 구하고

3. 첫 번째 원소값에서 지그재그를 하며 (r, c) 위치를 찾아 그 index 만큼 더해주자!

라는 아이디어를 떠올리게 됐다

 

 

 

✏️문제 풀이

1. 구현 - 오답

예제 1만을 가지고 풀었더니 1만 정답이고 나머지는 다 오답이다

왜 실패했을까 생각해봤는데

(r, c)를 한쌍으로 해서 정사각형으로 나눠야 하는데

나는 r 따로, c 따로 각각을 나누어 구한게 원인이지 않을까 싶다.

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

public class Main {
	static int N, r, c;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		
		int fullLength = (int) Math.pow(2, N);		// 한 변의 길이
		int rMid = (0 + fullLength) / 2;
		
		// 4-set의 첫 번째 원소 위치 찾기
		int startX = 0;
		while(true) {
			if(r == rMid) {
				startX = rMid;
				break;
			}
			
			if(r < rMid) {	// 0 ~ (rMid-1) 사이에 위치
				int tmp = rMid/2;
				if(tmp > 0) {		// 행을 4set씩 두 개 이상으로 여전히 분리할 수 있을 때
					rMid = tmp;
				}else {
					startX = rMid-2;
					break;
				}
			}else if(r > rMid) {		// rMid ~ (fullLneght-1) 사이에 위치
				int tmp = (rMid + fullLength) / 2;
				if(tmp > r) {		// 행을 4set씩 두 개 이상으로 여전히 분리할 수 있을 때
					rMid = tmp;
				}else {
					startX = rMid;
					break;
				}
			}
		}

		int startY = 0;
		int cMid = (0+fullLength) / 2;
		while(true) {
			if(c == cMid) {
				startY = cMid;
				break;
			}
			
			if(c < cMid) {	// 0 ~ (cMid-1) 사이에 위치
				int tmp = cMid/2;

				if(tmp >= 2) {		// 열을 4set씩 두 개 이상으로 여전히 분리할 수 있을 때
					cMid = tmp;
				}else {
					startY = cMid-2;
					break;
				}
			}else if(c > cMid) {		// cMid ~ (fullLneght-1) 사이에 위치
				int tmp = (cMid + fullLength) / 2;
				if(tmp > c) {		// 열을 4set씩 두 개 이상으로 여전히 분리할 수 있을 때
					cMid = tmp;
				}else {
					startY = cMid;
					break;
				}
			}
		}
		
		
		int result = 0;
		result += startX*fullLength;
		result += startY*2;

		int [] dx = {0, 0, 1, 1};
		int [] dy = {0, 1, 0, 1};
		
		for(int i = 0; i < 4; i++) {
			int tx = startX + dx[i];
			int ty = startY + dy[i];
			
			if(tx == r && ty == c) {
				result += i;		// index 0부터 시작
			}
		}
		
		System.out.println(result);
	}

}

 

 

2. 분할정복  - 성공

몇 번째 방문?

=> (내가 앞 사분면 * 그 사분면의 칸 수 = 이전사분면을 지나오면 누적된 개수) + 현재 속한 사분 사분면 내에서의 위치내가 속한 위치

 

 

이렇게 사분면을 잡아가며

현재 속한 구역의 크기를 줄여가며 현재 위치가 몇번째인지를 찾아가는거다.

사실 이렇게 해도 이해가 잘 안 될 수 있다

그래서 나는 직접 그려봤다

아래는 문제의 첫 번째 예제

2 3 1

로 풀어보는 과정이다.

 

2

 

첫 번째 시도

우선, N = 2,  fullLength = 2^2 = 4, mid = 2(한 사분면의 길이), count = mid*mid =4(한 사분면당 개수)

1. 현재 위치는 r = 3, c = 1 로 3사분면에 속한다.

2. 그럼 이전 사분면 까지의 개수를 더하고 (4*2 = 8)

3. 현재는 네 구역 중 하나의 사분명에 해당되지만, 이제는 이게 전체 사분면이 되도록 재귀

 -> 이때 포인트는

N-1, r = r-mid, c = c 이렇게 된다.

왜냐하면, 현재 사분면이 큰 정사각형이 되므로 현재 사분면의 천 번째 원소가 (0,0)으로 되기 때문이다

 

이렇게 하다 N == 0이 되는 순간 return하며 풀이는 끝난다.

 

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

public class Main {
	static int N, r, c;
	static int result = 0;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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());
		
		
		// 분할정복
		solve(N, r, c);
		
		// 출력
		System.out.println(result);
		
	}
	
	static void solve(int n, int x, int y) {
		if(n == 0) return;	// 더이상 구할 게 X
		
		int fullLength = (int) Math.pow(2, n);		// 전체 한변의 길이
		int mid = fullLength / 2;					//반으로 나눈 길이
		int count = mid*mid;			// 한 변이 mid인 정사각형 사분면에 해당되는 크기
		
		if(x < mid && y < mid) {	// 1사분면
			solve(n-1, x, y);		// 현재는 사분면 -> 다음 차례에는 full사각형
			
		}else if(x < mid && y >= mid ) {	// 2사분면
			result += count;
			solve(n-1, x, y - mid);		// (0, 0)이 시작점인 full 사각형으로 가니까 mid만큼 빼기
			
		}else if(x >= mid && y < mid ) {	// 3사분면
			solve(n-1, x-mid, y);
			result += count*2;
			
		}else {		// 4사분면
			solve(n-1, x-mid, y-mid);
			result += count*3;
		}
		
		
		
	}

}

 

 

'쪼갠다'는 아이디어는 잘 생각해냈지만

이를 '어떻게' 구현할 지 생각하는게 아직은 많이 부족한 것 같다고 느꼈다

'어떻게'를 생각해 내는 그 날까지, 부지런히 풀어야지