[백준/3020] 개똥벌래 (Java)
Question
-
분류 : 이진탐색
-
풀이 시간 : 90분
이분탐색은 진짜 쥐약인 분야...
많이 풀어서 접근하는 방법/시야를 키워야겠다
문제 해설
- 높이가 M, 길이가 N인 동굴에 위쪽에는 종유석이 달려있고, 밑에는 석순이 있음
- 종유석과 석순은 각각의 높이를 가지고 있고, 무조건 석순이 맨 먼저 시작함
- 개똥벌래는 구간을 직진해서 동굴을 지나감
- 개똥벌래는 장애물을 피하지 않아서, 지나가다가 종유석이나 석순을 만나면 부숨
- 구간마다 부숴야하는 개수가 다름
- 개똥벌래가 파괴해야하는 종유석+석순의 개수의 최솟값과 그런 구간이 몇개 있는지 구하시오
Solution
풀이 접근 방법
-
각 높이마다 종유석과 석순을 몇 개 통과할 수 있는지 구함
- 전체 개수 - 통과 개수 = 부수는 개수
- 각각 부수는 개수 를 더해서 최소가 될 때를 고르자
-
(밑에서 시작하는 높이 기준) 높이가 n일 때
- 아래에서부터 시작하는 석순은 n 높이를 지나간다 가정
- 위에 달려있는 종유석은 H(전체 높이) - n + 1 높이를 지나간다 가정
-
높이를 기준으로 해당 높이일 때 , 몇개를 부수지 않고 통과 가능한지 이분탐색
개똥벌래 이동 높이 석순 높이 통과 여부 3 2 부수지 않고 통과 가능 3 3 부숴야 통과 가능 3 4 부숴야 통과 가능 -
이분탐색 로직
-
높이 <= 석순 배열[이분 탐색 mid]
- mid 이후 값들은 다 부딪힘
- => 범위 왼쪽으로 이동
-
높이 > 석순 배열[이분 탐색 mid]
- mid 이전 값들은 모두 통과 가능
- => 더 가능한지 범위 오른쪽으로 이동
-
정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, H;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.valueOf(st.nextToken());
H = Integer.valueOf(st.nextToken());
// 종유석
Integer[] top = new Integer[N / 2];
// 석순
Integer[] down = new Integer[N / 2];
int tIdx = 0, dIdx = 0;
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
down[dIdx++] = Integer.valueOf(br.readLine());
} else {
top[tIdx++] = Integer.valueOf(br.readLine());
}
}
Arrays.sort(top);
Arrays.sort(down);
int totalObj = down.length;
int minBreak = Integer.MAX_VALUE;
int count = 0;
for (int i = 1; i <= H; i++) {
// 지나가는 구간이 i 높이일 때
// 전체 석순 개수 - 통과할 수 있는 개수
int downBreak = totalObj - passCntByBS(i, down);
// 전체 종유석 개수 - 통과할 수 있는 개수
int topBreak = totalObj - passCntByBS(H - i + 1, top);
int totalBreak = downBreak + topBreak;
if (totalBreak < minBreak) {
minBreak = totalBreak;
count = 1;
} else if (totalBreak == minBreak) {
count++;
}
}
bw.write(minBreak + " " + count + " \n");
bw.flush();
bw.close();
}
static int passCntByBS(int height, Integer[] arr) {
int start = 0;
int end = arr.length - 1;
int maxPass = 0;
while (start <= end) {
int mid = (start + end) / 2;
if (height <= arr[mid]) {
end = mid - 1;
} else {
// 구하는건 몇개를 pass하는지
// mid는 인덱스 값
// 만약 0번 idx가 통과 가능한거면 1개가 지나칠 수 있는 것
maxPass = Math.max(maxPass, mid + 1);
start = mid + 1;
}
}
return maxPass;
}
}
Author And Source
이 문제에 관하여([백준/3020] 개똥벌래 (Java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyunjkluz/백준3020-개똥벌래-Java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)