https://www.acmicpc.net/problem/3020
3020번: 개똥벌레
개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이
www.acmicpc.net
처음에는 2차원 배열로 만들어서 체크하는 방식으로 접근했는데, 생각보다 N과 M이 커서 메모리가 터졌습니다.
그래서 입력받으면서 구간합 느낌으로 더해줬습니다.
종유석을 top에 넣고,
석순을 bot에 넣어서
높이별로 수를 합산하여 가장 적게 걸리는 경우를 계산하여 출력했습니다.
public class BOJ_3020_개똥벌레 {
static Function<String, Integer> stoi = Integer::parseInt;
static int N, H;
static int[] top, bot;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi.apply(st.nextToken());
H = stoi.apply(st.nextToken());
top = new int[H + 2]; // 종유석
bot = new int[H + 2]; // 석순
for (int i = 0; i < N / 2; i++) {
bot[stoi.apply(br.readLine())]++;
top[H - stoi.apply(br.readLine()) + 1]++;
}
for (int i = H; i >= 1; i--) {
top[i] += top[i + 1];
}
for (int i = 1; i <= H; i++) {
bot[i] += bot[i - 1];
}
int min = Integer.MAX_VALUE;
int now = 0;
for (int i = 1; i <= H; i++) {
int obstacle = bot[H] - bot[i - 1] + top[1] - top[i + 1];
if (min > obstacle) {
min = obstacle;
now = 1;
} else if (min == obstacle) {
now++;
}
}
System.out.println(min + " " + now);
}
}