1074 Z

20200826 풀이

import java.util.Scanner;

public class Main_1074_Z {
	static int N, R, C;
	static int answer;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		C = sc.nextInt();

		find(N, 0, 0);
		System.out.println(answer);

		sc.close();

	}

	// (R,C)가 어떤 사분면에 위치하는가?
	// r, c 사분면 검사 시작 위치
	private static void find(int n, int r, int c) {
		int check = (int) Math.pow(2, n); // 검사할 범위의 행과 열 크기
		int pre = check / 2;
		if (n == 1) {
			answer += (R - r) * 2 + (C - c);
			return;
		}
		// 0<=r<2^N/2
		if (R >= r && R < (r + check / 2)) {
			// 1
			// 0<=c<2^N/2
			if (C >= c && C < (c + check / 2)) {
				find(n - 1, r, c);
			}
			// 2
			// 2^N/2<=c<2^N
			if (C >= (c + check / 2) && C < (c + check)) {
				answer += pre * pre * 1;
				find(n - 1, r, c + check / 2);
			}
		}
		// 2^N/2<=r<2^N
		if (R >= (r + check / 2) && R < (r + check)) {
			// 3
			// 0<=c<2^N/2
			if (C >= c && C < (c + check / 2)) {
				answer += pre * pre * 2;
				find(n - 1, r + check / 2, c);
			}
			// 4
			// 2^N/2<=c<2^N
			if (C >= (c + check / 2) && C < (c + check)) {
				answer += pre * pre * 3;
				find(n - 1, r + check / 2, c + check / 2);
			}
		}
		n -= 1;
	}
}

드.디.어 이 문제를 2일만에 풀었다ㅜㅜ 역시 개념을 공부해야한다 공부하고 푸니까 더 쉽게 풀 수 있었다. 이제 재귀문제 나오면 바로 풀 수 있지?!

 

내가 처음에 푼 방법

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int r = sc.nextInt();
		int c = sc.nextInt();
		int answer = 0;

		// (0,0)=1 (0,1)=2 (1,0)=3 (1,1)=4
		if (r <= 1 && c <= 1) {
			answer = (r * 2 + c);
		} else {
			// mod로 나눈 몫은 시작점
			// 나머지는 4칸에서의 위치
			int mod = 2;
			answer += ((r % 2)*2 + c % 2);
			while (true) {
				r /= 2;
				c /= 2;
				mod *= 2;
				answer += mod * (r * 2 + c);
				if (r == 1 || c == 1) {
					break;
				}
			}
		}
		System.out.println(answer);
	}
}

나름 공식을 구해봤는데 이제 이렇게 하지말고 알고리즘 공식을 적용해서 푸는 연습을 해야겠다.

 

분할정복으로 푼 방법

import java.util.Scanner;

public class Main {

	static int r, c;
	static int answer;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		r = sc.nextInt();
		c = sc.nextInt();

		sc.close();
		recursion((int) Math.pow(2, N), 0, 0);

	}

	private static void recursion(int len, int x, int y) {
		if (x == r && y == c) {
			System.out.println(answer);
			System.exit(0);
		}
		if (len == 1) {
			answer++;
			return;
		}
		if (!(x <= r && r < len + x && y <= c && c < len + y)) {
			answer += len * len;
			return;
		}
		int next_len = len / 2;
		recursion(next_len, x, y);
		recursion(next_len, x, y + next_len);
		recursion(next_len, x + next_len / 2, y);
		recursion(next_len, x + next_len, y + next_len);
	}
}

분할정복을 정확하게 모르겠어서 일단 따라해봤다. 근데 틀렸습니다라고 뜬다 :/ 어디가 문제일까

분할정복은 같은게 반복(재귀)되니까 작게 나눠서 하나씩 결과 구하는 방법?인듯하다.

배웠던거같은데 기억이 안난다.

 

---

질문 게시판에서 찾은 반례는

 

1 0 0 : 0으로 나눴을 때 오류

3 1 5 : 19

3 3 1 : 11

3 0 4 : 16

5 2 26 : 332 (여기서 틀렸다는것을 알 수 있었다. 나는 60이 나오는데 분할정복은 잘 나온다. 다시 생각해봐야겠다.)

 

---

https://worldforest9.tistory.com/entry/%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

[재귀] 분할정복 문제 풀기