[백준/분할정복] 1074: Z - 자바

문제

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

1074번: Z

 

풀이

분할정복을 이용하는 전형적인 문제

처음에 좌표 r, c 의 순서를 구할 때 좌표 r,c 가 속해있는 사분면까지 순서를 모두 구했는데 시간 초과가 발생하였다.

 

이 문제는 구하려는 좌표가 1,2,3,4 분면 어느곳에 위치한지 먼저 파악한 후에 사분면 1개의 크기가 1이 될때까지

좌표 r,c의 사분면을 구하면서 이전 사분면들의 크기를 모두 더하면 된다.

 

재귀를 이용하여 각 사분면을 나누었다. 

 

Sol1

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

public class BOJ_1074 {
	static int cnt, r, c;
	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());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		solution((int) Math.pow(2, N), 0, 0);
	}
	
	public static void solution(int size, int y, int x) {
		if(y == r && x == c) {
			System.out.println(cnt);
			System.exit(0);
		}
		
		if (y <= r && r < y + size && x <= c && c < x + size) {
			size = size / 2;
			solution(size, y, x); // 1
			solution(size, y, x + size); // 2
			solution(size, y + size, x); // 3
			solution(size, y + size, x + size); // 4
			
		} else cnt += size*size;
	}
}

 

풀이2 도 마찬가지로 재귀를 이용하였다. 풀이1과 접근 방법은 비슷하다.

size를 줄이면서 해당 사분면의 크기를 더해주었다.

 

Sol2

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

public class BOJ_1074_Sol2 {
	static int ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		solve((int)Math.pow(2, Integer.parseInt(st.nextToken())), 
        Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()) );
		System.out.println(ans);
	}
	
	public static void solve (int n, int r, int c) {
		if(n == 2) {
			if(r == 0 && c == 1) ans+=1; // 2사분면
			else if(r == 1 && c == 0) ans+=2; // 3사분면
			else if(r == 1 && c == 1) ans+=3; // 4사분면
			return;
		}
			
		int half = n / 2;
		int skip = 3; // 기본은 4사분면에 있다고 가정
		if     (r <  half && c <  half) skip = 0;
		else if(r <  half && c >= half) skip = 1;
		else if(r >= half && c <  half) skip = 2;
		ans += half * half * skip;
		solve(half, r % half, c % half);
	}
}

 

풀이3은 풀이1, 2와 다르게 반복을 이용하였다. 

Sol3

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

public class BOJ_1074_Sol3 {
	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 n = (int)Math.pow(2, N) / 2;
		int ans = 0;
		while (N-- > 0) {
			int skip = 3;
			if 		(r <  n && c <  n) skip = 0;  // 1사분면
			else if (r <  n && c >= n) skip = 1;  // 2사분면
			else if (r >= n && c <  n) skip = 2;  // 3사분면
			
			ans += n * n * skip;
			r %= n;
			c %= n;
			n = (int)Math.pow(2, N) / 2;
		}
		System.out.println(ans);
	}
}