3020 개똥벌레

3020 개똥벌레 / c++ / Gold5 / 1시간 4분

문제 및 코드

풀이 과정

누적합

1. 길이가 N이고 높이가 H인 동굴에 1미터마다 종유석(바닥에서 위로 커지는 돌)과 석순(위에서 아래로 커지는 돌)이 번갈아 등장한다. 한 높이로 일정하게 장애물을 부수며 날아갈 때, 장애물의 최솟값과 그러한 구간의 수를 출력하는 문제.
2. 우선 주어진 데이터를 가공한다.
3. 여기서는, 번갈아 등장하는 종유석과 석순을 우선 두 벡터로 나눠서, 각각 등장하는 높이(index)와 등장하는 횟수(value)를 저장한다.
4. 다음으로 알 수 있는 사실은, 높이가 N일 때, N이상의 높이를 가지는 모든 돌에 부딪히는다는 점이다.
5. 따라서 두 벡터를 내림차순으로 순회하며 누적합 연산을 한다. (Vector[N] += Vector [N+1])
6. 다음으로 높이를 1부터 H까지 순회하면서 각 높이에 대해 부딪히는 장애물 개수를 구한다.
   (이 때 주의해야 할 점은, 종유석 배열은 현재 높이를 그대로 인덱스로 사용해도 되지만, 석순은 [최대 높이 - 현재 높이 + 1] 값을 인덱스로 사용해야 함)
   1. 만약 현재 장애물의 개수가 기존의 최소값보다 작다면
      1. 최소값을 갱신
      2. 구간의 개수도 1로 초기화
   2. 만약 현재 장애물의 개수가 기존의 최소값과 같다면
      1. 구간의 개수를 1 증가
7. 6번의 순회가 끝난 뒤에 최소값과 그 구간의 개수를 출력
8. 해결

회고

1. 오랜만에 다시 골드 문제로 넘어왔다. 문제의 유형은 금방 파악했지만, 그림으로 표현하지 않고 머리속으로만 계산했더니 헷갈려서 시간을 오래 소비했다. 다음부터는 그냥 바로 그림으로 그려봐야겠다.
2. 처음에 석순에 대한 인덱스 계산을 그냥 [최대 높이 - 현재 높이] 로만 해서 제대로 된 결과값이 나오지 않았었다. 분명 높이 0은 없는데, 이것도 그림으로 표현해보니 바로 해결됐었다.