[알고리즘][X] Z
2024. 2. 14. 13:53ㆍ알고리즘 풀이/Java
https://www.acmicpc.net/problem/1074
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))); 로 바꾸어 주었다.
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘][X] 월드컵 (0) | 2024.02.15 |
---|---|
[알고리즘] 빵집 (1) | 2024.02.14 |
[알고리즘] 쿼드트리 (1) | 2024.02.14 |
[알고리즘] 설탕 배달 (0) | 2024.02.13 |
[알고리즘] 중위 순회 (0) | 2024.02.12 |