[백준] No.3020 - 개똥벌래 (C++, 부분합)

문제

 

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

3020번: 개똥벌레

 

 

풀이

 

solved.ac 난이도: Gold 5

 

 

이진 탐색으로 더 간단히 푸는 방법이 있지만 부분합 알고리즘만으로 해당 문제를 풀어보았다.

 

아래에서부터 올라오는 석순은 석순의 끝이 도달하는 구간에 

위에서부터 내려오는 종유석은 그 끝이 도달하는 구간에 각각 해당 개수를 기록한다.

 

석순은 section_down, 종유석은 section_up에 각각 저장.

for(int idx=0; idx<cave_len ; ++idx){
  cin>>temp;
  if(idx % 2 ==0)
    ++section_down[temp];
  else
    ++section_up[cave_height -temp +1];
}

 

이제 석순만을 생각해보자.

구간 1에서는 1m 이상의 석순의 개수,

구간 2에서는 2m이상의 석순의 개수,

...

구간 H에서는 Hm이상의 석순의 개수가 해당 구간에서 장애물의 개수가 된다.

 

따라서 각 구간에서의 장애물 개수는 동굴의 높이인 H에서부터 -1m씩 내려오며 section_down의 연속합 계산을 해준다.

 

for(int h=cave_height-1; h>0; --h)
  section_down[h] += section_down[h+1];

 

반대로 위에서 부터 내려오는 종유석만 생각해보자.

구간 H에서는 1m이하의 종유석의 개수,

구간 H-1에서는 2m이하의 종유석의 개수,

...

구간 1에서는 Hm이하의 종유석의 개수가 해당 구간에서 장애물의 개수가 된다.

 

따라서 section_up은 2m에서 Hm까지 올라가면서 section_up의 연속합을 구해준다.

 

for(int h=2; h<=cave_height ; ++h)
  section_up[h] += section_up[h-1];

 

이제 각 구간에서 지나게되는 종유석과 석순의 개수를 구했으므로 

h구간에서 지나는 장애물의 총 개수는 아래와 같이 구할 수 있다.

section_up[h] + section_down[h]

 

최종적으로 최솟값과 최솟값을 갖는 구간의 개수를 구해주면 된다.

 

이진 탐색으로는 더 빠르게 풀 수 있지만 연속합을 이용하면 한 번씩만 순회하는 것으로 해결할 수 있기 때문에

시간 복잡도는 O(N + 3*H)로 충분히 시간 안에 해결 가능하다.

 

코드