[BaekJoon] 개똥벌레 c++ , java

문제 

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

입출력 예

6 7
1
5
3
3
5
1

2 3

풀이

장애물은 석순 → 종유석 순으로 번갈아 가며 위치하고 있습니다. 

아래는 입출력 예를 도식화한 그림입니다.

장애물이 걸리는 최초 높이에 +1를 합니다.

bottom[1] = bottom[3] = bottom[5] = 1,

top[3] = top[5] = top[7] = 1

 

bottom배열은 높이 1,3, 5에 장애물이 나타납니다. 

높이 1일 때 장애물 1, 3, 5 모두 파괴됩니다.

높이 3일 때 장애물 3, 5 가 파괴됩니다.

높이 5일 때 장애물 5 가 파괴됩니다.

→이제, prefix sum을 활용하여 문제를 풀 수 있습니다.

높이를 나타내는 bottom배열 인덱스를 이전 값과 더하기 누적을 통해 높이에 따른 장애물 개수를 셀 수 있습니다.

 

top배열은 높이 3, 5 ,7에 장애물이 나타납니다.

높이 7일 때 장애물 3, 5, 7 모두 파괴됩니다.

높이 5일 때 장애물 3, 5 가 파괴됩니다.

높이 3일 때 장애물 3 이 파괴됩니다.

→이제, postfix sum을 활용하여 문제를 풀 수 있습니다.

높이를 나타내는 top배열 인덱스를 다음 값과 더하기 누적을 통해 높이에 따른 장애물 개수를 셀 수 있습니다.

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <climits>
using namespace std;


int main() {

	int n = 0, h = 0;
	scanf_s("%d %d", &n, &h);

	int len = n > h ? n : h;
	vector<int> top(len + 1, 0), bottom(len + 1, 0);

	int num = 0;
	for (int i = 0; i < n; i++) {
		scanf_s("%d", &num);
		if (i % 2 == 0) {
			bottom[num]++;
		}
		else {
			top[h - num + 1]++;
		}
	}

	for (int i = 1; i <= h; i++) {
		top[i] += top[i - 1];		//이전 값 누적 합
		bottom[h - i] += bottom[h - i + 1]; //다음 값 누적 합
	}

	long long ans = LONG_MAX;
	int cnt = 0;
	for (int i = 1; i <= h; i++) {
		if (top[i] + bottom[i] < ans) {
			cnt = 1;
			ans = top[i] + bottom[i];
		}
		else if (top[i] + bottom[i] == ans) {
			cnt++;
		}
	}

	printf_s("%lld %d", ans, cnt);

	return 0;
}

 

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	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 len = N > H ? N : H;

        int[] top = new int[len + 1];
        int[] bottom = new int[len + 1];

        for(int i = 0; i < N; i++){
            int a = Integer.parseInt(br.readLine());
            if(i % 2 == 0){
                bottom[a]++;
            }
            else{
                top[ H - a + 1 ]++;
            }
        }

        for(int i = 1; i <= H; i++){
            top[i] += top[i-1];
            bottom[H - i] += bottom[H - i + 1];
        }

        long ans = Long.MAX_VALUE;
        int cnt = 0;
        for(int i = 1; i <= H; i++){
            if(top[i] + bottom[i] < ans){
                cnt = 1;
                ans = top[i] + bottom[i];
            }
            else if(top[i] + bottom[i] == ans){
                cnt++;
            }
        }
        System.out.println(ans + " " + cnt);
    }


}