백준 3020번: 개똥벌레 (Java)

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

3020번: 개똥벌레

 

---

 

풀이

장애물이 있는 범위를 누적합을 통해 구하면 됩니다: 가령, H=7이고 석순의 길이가 3이라면, 1, 2, 3이 영향을 받으므로, '석순 배열'의 3번째 index에 1을 넣고, H에서부터 1까지 누적합을 구하면 높이가 3인 석순이 1, 2, 3에 영향을 끼친다는 것을 구현할 수 있습니다. 반대로, 종유석의 길이가 3이라면 이는 7, 6, 5에 영향을 미치기에, '종유석 배열'의 5(=H+1-종유석의 길이)번째 index에 1을 넣고 1부터 H까지 누적합을 구하면 7, 6, 5에 영향을 끼치는 걸 구현할 수 있습니다.

 

배운 점

정렬해서 하나하나 찾아보는 O(NlogN) 풀이로 풀긴 했는데, 누적 합 풀이는 왜이리 생각이 나지 않을까? 진짜 약점인가봐... :(

 

코드

import java.io.*;
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[] up = new int[H+1];
        int[] down = new int[H+1];
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) up[Integer.parseInt(br.readLine())]++;
            else down[H+1-Integer.parseInt(br.readLine())]++;
        }
        
        for (int i = 1; i <= H; i++) {
            up[H-i] += up[H+1-i];
            down[i] += down[i-1];
        }
        
        int ans = N;
        int cnt = 0;
        for (int i = 1; i <= H; i++) {
            // 닿는 종유석의 개수
            int temp = up[i] + down[i];
            if (temp < ans) {
                ans = temp;
                cnt = 1;
            } else if (temp == ans) {
                cnt++;
            }
        }
        System.out.println(ans + " " + cnt);
    }
 
}