문제
https://www.acmicpc.net/problem/3020
풀이
누적합을 이용해 해결한 문제입니다. 입력값이 2 ≤ N ≤ 200,000, 2 ≤ H ≤ 500,000 으로 주어지기 때문에, 이중 for문을 돌면 바로 시간 초과에 걸리게 됩니다.
문제 상황을 위처럼 그림으로 나타내볼 수 있었습니다. 각 높이별로 파괴해야하는 장애물의 개수을 표시한 것입니다.
저 개수를 어떻게 구해야할지 생각해보다가 우선 석순과 종유석 배열을 각각 나누어야겠다고 생각했습니다.
그래서 우선 입력을 석순과 종유석(bottom[], up[])배열에 나누어서 받았습니다.
이 때, 주어지는 입력 값인 장애물의 크기는 bottom[], up[] 배열의 인덱스로 입력받아, 해당하는 인덱스 배열의 값을 +1 해줍니다.
그러면 우선, 그림처럼 나오게 됩니다.
이 때 한번에 높이별 합을 구하지 않는 것은 이중 for문을 돌면 시간초과가 발생하기 때문입니다.
이제 이 값을 통해 누적합을 구할 수 있습니다. 한 번의 for문을 돌면서 이전 인덱스를 누적합 시키면 됩니다.
bottomSum[i+1] += bottomSum[i];
식을 통해 누적합을 구한 그림은 위와 같고 up[] 배열도 마찬가지 과정을 진행해주면 됩니다.
그리고 두 배열을 합쳐, 높이별 장애물 개수를 구할 수 있습니다.
아래는 소스 코드입니다.
소스 코드
import java.util.Arrays;
import java.util.Scanner;
public class B3020_개똥벌레 {
static int[] bottomSum;
static int[] upSum;
static int[] prefixSum;
static int N,H;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
H = sc.nextInt();
bottomSum = new int[H];
upSum = new int[H];
prefixSum = new int[H];
for(int i = 0;i<N/2;i++){
int b = sc.nextInt()-1;
int u = sc.nextInt()-1;
bottomSum[b]++;
upSum[H-1-u]++;
}
for(int i =0;i<H-1;i++){
upSum[i+1] += upSum[i];
bottomSum[H-(i+2)] += bottomSum[H-(i+1)];
}
for(int i =0;i<H;i++){
prefixSum[i] = upSum[i]+bottomSum[i];
}
Arrays.sort(prefixSum);
int cnt = 0;
for(int i = 0;i<H;i++){
if(prefixSum[0]==prefixSum[i]) cnt++;
else break;
}
System.out.println(prefixSum[0]+" "+cnt);
}
}
'Java > BOJ' 카테고리의 다른 글
[BOJ] 백준 17073. 나무 위의 빗물 (0) | 2024.05.12 |
---|---|
[BOJ] 백준 14267. 회사 문화 1 (0) | 2024.05.10 |
[BOJ] 백준 1063. 킹 (0) | 2024.05.07 |
[BOJ] 백준 18223. 민준이와 마산 그리고 건우 (0) | 2024.05.06 |
[BOJ] 백준 15681. 트리와 쿼리 (0) | 2024.05.04 |