3020 개똥벌레
-
백준 3020 개똥벌레Algorithm/BOJ 2021. 3. 31. 11:36
출처: www.acmicpc.net/problem/3020 분류: 이분탐색 접근방식 이 문제는 가로 20 세로 50만이므로 모두 탐색한다거나 h만큼 일일이 배열에 담아준다거나 하는 방식으로는 시간초과를 면하기 어렵습니다. 저희가 원하는 건 특정 높이에서 만나는 장애물의 개수 입니다. 순서는 상관이 없죠! 따라서 이분탐색을 떠올려볼 수 있습니다. 대신 종유석과 석순이 서로 반대방향으로 나있기 때문에 이분탐색 upper/lower 바운드를 잘 섞어서 사용해줘야 하겠습니다. 이분탐색 upper/lower bounds가 익숙하지 않으시다면 여기를 읽어주세요 :] 조금 더 구체적으로 알아볼게요. 석순과 종류석의 높이를 따로 배열에 담고 정렬해줍니다. 저는 석순이 난 방향부터 높이를 1로 생각해서 계산해보려고 합니..