BOJ : 3020

1. 문제

 

2. 문제 설명과 알고리즘 설계

 

사실 이 문제 입력부터 이해가 잘 가지 않아서 다른 사람의 풀이를 참고하였다.

 

구간별로 석순과 종유석의 개수를 구하는 문제이다. 각각 높이에 따라 석순과 종유석의 개수를 누적하는 up, down 배열을 생성한다.

 

누적합을 구한 후, 첫 번째 구간부터 H번째 구간까지 차례대로 장애물의 수를 확인한 다음, min과 cnt을 갱신해준다.

 

i번째 구간에서의 석순의 개수는 bot[H] - bot[i-1]

i번째 구간에서의 종유석의 개수는 top[H] - top[i+1] 로 구할 수 있다.

이 두 결과를 더한 값이 i번째 구간에서의 장애물의 총 개수가 된다.

int obs = (bot[H] - bot[i - 1]) + (top[1] - top[i + 1]);

 

3. 코드

package week8;

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

public class Q3020_boj {
    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 up[] = new int[H+2];
        int down[] = new int[H+2];

        for (int i = 0; i < N/2; i++) {
             down[Integer.parseInt(br.readLine())]++;
             up[H-Integer.parseInt(br.readLine())+1]++;
        }

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

        for (int i = H; i >= 1; i--) {
            up[i] += up[i+1];
        }

        int min = N;
        int cnt = 0;

        for (int i = 1; i <= H; i++) {
            int obs = (down[H] - down[i - 1]) + (up[1] - up[i + 1]);

            if (obs < min) {
                min = obs;
                cnt = 1;
            } else if (obs == min)
                cnt++;
        }

        System.out.println(min + " " + cnt);
    }
}

 

4. 시간복잡도

 

O(N)

 

5. 결과