[PS] 백준3020 : 개똥벌레(Java)CS/알고리즘2024. 10. 10. 16:41
Table of Contents
문제
https://www.acmicpc.net/problem/3020
풀이
누적합을 활용한 풀이
접근법
N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.
단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다.
그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까?
처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.
N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.
결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 해당하는 구간이 몇개 있는지 순회하는 것으로 마무리했다.
아래는 위 접근에 대한 코드.
소스코드
import java.io.*;
import java.util.*;
//BOJ_3020
public class Main {
static int N, H;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken()); //높이
int[] left = new int[H+1]; //종유석
int[] right = new int[H+1]; //석순
for(int i=0; i<N; i++) {
int idx = Integer.parseInt(br.readLine());
if(i % 2 == 0) {
//석순 left
left[idx]++;
}
else {
right[H+1-idx]++;
}
}
for(int i=H-1; i>0; i--) {
left[i] += left[i+1];
}
for(int i=1; i<=H; i++) {
right[i] += right[i-1];
}
int[] res = new int[H+1];
int min = Integer.MAX_VALUE;
for(int i=1; i<=H; i++) {
res[i] = left[i] + right[i];
min = Math.min(min, res[i]);
}
int ans = 0;
for(int i=1; i<=H; i++) {
if(res[i] == min) ans++;
}
System.out.println(min + " " + ans);
}
}
정리
입력이 굉장히 클 경우에 다양한 알고리즘을 생각해볼 수 있는데, 일반적으로 알아두어야 할 것으로는 dp, 누적합, 구간합, 이분탐색 정도가 필수라고 생각한다.
이미 이러한 유형에 대해서 많이 데여본 경험이 있기 때문에 정리해두었던게 이번 문제를 빠르게 풀 수 있었던 키 포인트!
'CS > 알고리즘' 카테고리의 다른 글
[PS] 백준17485 : 진우의 달 여행 (Large)(Java) (3) | 2024.10.24 |
---|---|
[PS] 프로그래머스 Lv4 : 도둑질(Java) (0) | 2024.10.14 |
[PS] 백준1339 : 단어 수학(Java) (0) | 2024.10.07 |
[PS] 백준13305 : 주유소(Java) (0) | 2024.10.05 |
[코드트리 조별과제] 4주차 학습 (정렬 알고리즘) (6) | 2024.08.10 |
@Beemo9 :: BeHinD
개발 기술 블로그, Dev
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!