개발일지/Algorithm
백준 - 3020 개똥벌레 [누적합][이모스]
3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 요약 장애물의 위치가 주어지고, 해당 장애물을 통과하는 최솟값과 그러한 구간의 수를 출력하라 2. 접근 방법 위와 같은 장애물이 있다고 했을 때, 아래서부터 장애물을 통과하는 수를 세어보면 3, 3, 2, 3 입니다. 이런 식으로 완전탐색으로도 충분히 정답은 구할 수 있습니다만, 시간과 메모리가 한정되어 있기 때문에 다른 방법으로 풀어야 합니다. 이모스법 알고리즘을 알고 있다면 쉽게 풀 수 있습니다. 위 그림과 같이 장애물이 시작되는 위치에 +1, 끝나는..
