728x90
๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
โ๏ธSolution
์ด๋ถ ํ์(Binary Search) ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ํ ์ ์์ต๋๋ค. ์ฌ๋ ์์น๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ ๋ค, ๋๋ฌผ๋ค์ ์์น๋ฅผ ์ํํ๋ฉด์ L ์ฌ๊ฑฐ๋ฆฌ ๋ด์ ๋ค์ด์ค๋ ์ฌ๋๋ฅผ ์ฐพ์ผ๋ฉด ๋ฉ๋๋ค. ์ฆ, ๋ก์ง์ ์์๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
- ์ฌ๋ ์์น ๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ
- ๋๋ฌผ๋ค์ ์ขํ๋ฅผ ์ํ
- ํ์ฌ ๋๋ฌผ์ x ์ขํ์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ฌ๋์ ์ขํ๋ฅผ ํ์ (y ์ขํ๋ ๊ณ ์ ๊ฐ์ด๊ธฐ์ ์์๋ก ํญ์ ์๋ ์)
- ํ์ํ ์ฌ๋์์ ๊ฑฐ๋ฆฌ๊ฐ L ์ดํ์ด๋ฉด ํ์ ์ข
๋ฃ
- ์ก์ ์ ์๋ ๋๋ฌผ ์ +1ํ๊ณ , ๋ค์ ๋๋ฌผ ์ขํ๋ก ์ํ
- ํ์ํ ์ฌ๋์์ ๊ฑฐ๋ฆฌ๊ฐ L๋ณด๋ค ํฌ๋ค๋ฉด, ํ์ฌ ๋๋ฌผ์ x ์ขํ์์ ์ฌ๋๊ฐ ์ผ์ชฝ์ ์๋์ง ์ค๋ฅธ์ชฝ์ ์๋์ง ํ์
- ์ฌ๋๊ฐ ์ผ์ชฝ์ ์๋ค๋ฉด left = mid + 1
- ์ฌ๋๊ฐ ์ค๋ฅธ์ชฝ์ ์๋ค๋ฉด right = mid - 1
๐ง๐ป๐ปSource Code
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ8983 {
private static int M, N, L;
private static long[] ShootingPositions;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);
String[] inputs = br.readLine().split(" ");
M = Integer.parseInt(inputs[0]);
N = Integer.parseInt(inputs[1]);
L = Integer.parseInt(inputs[2]);
inputs = br.readLine().split(" ");
ShootingPositions = new long[M];
for (int i = 0; i < M; i++) {
ShootingPositions[i] = Long.parseLong(inputs[i]);
}
Arrays.sort(ShootingPositions);
int answer = 0;
for (int i = 0; i < N; i++) {
inputs = br.readLine().split(" ");
long x = Long.parseLong(inputs[0]), y = Long.parseLong(inputs[1]);
answer += binarySearch(0, M - 1, x, y);
}
System.out.println(answer);
br.close();
}
public static int binarySearch(int left, int right, long animalX, long animalY) {
boolean canHunt = false;
while (left <= right) {
int mid = (left + right) / 2;
long turretX = ShootingPositions[mid];
long distance = Math.abs(turretX - animalX) + animalY;
// ์ฌ๋ฅ ๊ฐ๋ฅํ ๊ฑฐ๋ฆฌ์ด๋ฉด ์ด๋ถ ํ์ ์ค๋จ
if (distance <= L) {
canHunt = true;
break;
}
if (turretX < animalX) left = mid + 1;
else right = mid - 1;
}
return canHunt ? 1 : 0;
}
}
728x90
๋ฐ์ํ
'๐คAlgorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 2477๋ฒ | ์ฐธ์ธ๋ฐญ (Java) (0) | 2024.07.30 |
---|---|
[BOJ] 20056๋ฒ | ๋ง๋ฒ์ฌ ์์ด์ ํ์ด์ด๋ณผ (Java) (1) | 2024.07.25 |
[BOJ] 12904๋ฒ | A์ B (C++) (0) | 2024.03.28 |
[BOJ] 14891๋ฒ | ํฑ๋๋ฐํด (C++) (0) | 2024.03.24 |
[BOJ] 2636๋ฒ | ์น์ฆ (C++) (1) | 2024.03.22 |