[알고리즘][X] Z

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

1074번: Z

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception {
		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());		
		
		System.out.println(findVisitTime(N, r, c));

	}

	private static int findVisitTime(int n, int r, int c) {
		if (n == 0) {
			return 0;
		}
		
		int areaNumber = findWhichArea(n, r, c);
		int result = (areaNumber - 1) * ((int) (Math.pow(2, n) / 4 * Math.pow(2, n)));
		int N = (int) Math.pow(2, n);
		if (areaNumber == 2) {
			c -= N / 2;
		} else if (areaNumber == 3) {
			r -= N / 2;
		} else if (areaNumber == 4) {
			r -= N / 2;
			c -= N / 2;
		}
		result += findVisitTime(n - 1, r, c);
		return result;
	}

	private static int findWhichArea(int n, int r, int c) {
		int N = (int) Math.pow(2, n);
		if (0 <= r && r <= (N-1) / 2 && 0 <= c && c <= (N-1) / 2) {
			return 1;
		}
		if (0 <= r && r <= (N-1) / 2 && (N+1) / 2 <= c && c <= (N-1)) {
			return 2;
		}
		if ((N + 1) / 2 <= r && r <= N-1 && 0 <= c && c <= (N-1) / 2) {
			return 3;
		}
		if ((N + 1) / 2 <= r && r <= N-1 && (N+1) / 2 <= c && c <= (N-1)) {
			return 4;
		}
		return 0;
	}
}

나의 풀이

- int result = (areaNumber - 1) * ((int) (Math.pow(2, n) * Math.pow(2, n))) / 4;

- 위와 같이 해주었었는데 이렇게 되면 3 * 2^30이 되는데 2^31을 넘어서게 되므로 오버플로우 문제가 발생하게 된다.

- 따라서 int result = (areaNumber - 1) * ((int) (Math.pow(2, n) / 4 * Math.pow(2, n))); 로 바꾸어 주었다.