[BOJ C++] 3020 개똥벌레

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

3020번: 개똥벌레

 

 

문제 이해

동굴에는 종유석과 석순이 자랍니다. 석순은 밑에서 부터, 종유석은 위에서 부터 자랍니다. 개똥벌레는 이 장애물들을 피하지 않으며 뚫고 지나갑니다. 개똥벌레가 최소한의 장애물들을 부수며 갔을 때 부순 갯수와 그러한 루트가 몇개나 있는지 구하는 문제였습니다.

 

 

입출력 조건

시간초 제한은 1초, 동굴의 크기가 200,000 x 500,000이 최대크기라 절대 단순반복으로는 풀 수 없었습니다.

 

 

풀이

생각하느라 오래 걸렸었습니다.

입력을 받을 때 석순 혹은 종유석이 몇번높이까지 가있는지를 확인하여 저장하고 종유석은 끝나는 지점부터 위로, 석순은 끝나는 지점부터 아래로 누적합을 구해주었습니다. 한번 그려보면 쉽게 알 수 있습니다.

이렇게 구한 누적합을 가지고 높이별로 개똥벌레를 이동시켜 보고 정답을 구할 수 있었습니다.

 

 

에러 및 느낀 점

풀이 방법을 생각해 내기 어려운 문제였습니다.

처음에는 이분탐색인가 하였지만 누적합으로 문제를 해결하였습니다.

 

 

전체 코드

https://github.com/JuneYoungDo/Algorithm/blob/master/3020_%EA%B0%9C%EB%98%A5%EB%B2%8C%EB%A0%88.cpp

GitHub - JuneYoungDo/Algorithm: This is a repository for additional problem solving in Baekjun.