728x90
문제
https://www.acmicpc.net/problem/3020
3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
풀이
처음에 문제를 읽었을 때 정말 쉬운 문제라고 생각했음
근데 또 문제 안읽어서 주어지는 수들의 범위를 체크를 못함 또 또또 ㅠㅠㅠㅠ
1번 방법(오답)
그냥 높이별 부딪히는 횟수를 계산할 배열을 만들고 2중 for문을 돌면서 해당 배열에 저장해줌!
이렇게 풀면 당연히 시간초과,,,,
2번 방법(정답)
이분 탐색!
오답 코드
// 3020번 개똥벌레
// https://www.acmicpc.net/problem/3020
package BAEKJOON;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Num3020_개똥벌레 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[] answerArr = new int[H + 1];
int[] down = new int[N / 2];
int[] up = new int[N / 2];
for (int i = 0; i < N; i++) {
if (i % 2 != 0) { // 종유석이면
up[i / 2] = Integer.parseInt(br.readLine());
} else { // 석순이면
down[i / 2] = Integer.parseInt(br.readLine());
}
}
int min = Integer.MAX_VALUE;
for (int i = 1; i <= H; i++) {
for (int j = 0; j < N / 2; j++) {
if (i <= down[j]) {
answerArr[i]++;
}
if (i > H - up[j]) {
answerArr[i]++;
}
}
if (min > answerArr[i]) {
min = answerArr[i];
}
}
int count = 0;
for (int i = 0; i < answerArr.length; i++) {
if (answerArr[i] == min) {
count++;
}
}
System.out.println(min + " " + count);
}
}
정답 코드
// 3020번 개똥벌레
// https://www.acmicpc.net/problem/3020
package BAEKJOON;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Num3020_개똥벌레 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[] answerArr = new int[H + 1];
int[] down = new int[N / 2];
int[] up = new int[N / 2];
for (int i = 0; i < N; i++) {
if (i % 2 != 0) { // 종유석이면
up[i / 2] = Integer.parseInt(br.readLine());
} else { // 석순이면
down[i / 2] = Integer.parseInt(br.readLine());
}
}
int min = Integer.MAX_VALUE;
for (int i = 1; i <= H; i++) {
for (int j = 0; j < N / 2; j++) {
if (i <= down[j]) {
answerArr[i]++;
}
if (i > H - up[j]) {
answerArr[i]++;
}
}
if (min > answerArr[i]) {
min = answerArr[i];
}
}
int count = 0;
for (int i = 0; i < answerArr.length; i++) {
if (answerArr[i] == min) {
count++;
}
}
System.out.println(min + " " + count);
}
}728x90