[백준]1074번 Z(JAVA)

0. 문제 링크

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

1074번: Z

 

1. 문제 설명

1) 2^N * 2^N 크기의 배열을 방문할 때 r행 c열을 몇 번째로 방문하는지 구하기

 

2. 입출력

// input
2 3 1 // N, r, c

// output
11

 

3. 코드

import java.util.Scanner;

public class b1074 {
	static int cnt = 0;

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

		recursive(r, c, (int)Math.pow(2, N));
		
		System.out.println(cnt);
	}

	private static void recursive(int r, int c, int size) {
		// basis part
		if(size == 1) { // size가 1이 되면 종료
			return;
		}
		
		// inductive part
		int half = size / 2;
		if(r < half && c < half) { // 1사분면
			recursive(r, c, half);
		} else if(r < half && c >= half) { // 2사분면
			cnt += (size * size) / 4;
			recursive(r, c-half, half);
		} else if(r >= half && c < half) { // 3사분면
			cnt += (size * size) / 4 * 2;
			recursive(r-half, c, half);
		} else if(r >= half && c >= half) { // 4사분면
			cnt += (size * size) / 4 * 3;
			recursive(r-half, c-half, half);
		}
		
	}

}

 

실행 결과

 

4. 회고

1) Math.pow 사용할 때는 return 값이 double이므로 int로 명시적 형변환을 해야함을 유의

2) 사분면을 이용한 문제는 처음 해결해보는데, 각 사분면에서 cnt 값을 조절하면서 재귀로 해결할 수 있음

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b1074.java