shie44167   7달 전

22%에서 시간초과가 납니다 이분탐색도 쓰고 정렬도 했지만 시간초과가 나네요 복잡해서 그런가 ㅎㅎ...

1. 종유석과 석순을 구분해서 입력 받았습니다. 종유석은 h에서 빼서 바닥부터 빈칸이 몇 칸인지로 처리했고요.

2. 정렬 한 뒤에 1~h 높이 까지 개똥벌레가 얼마나 적게 장애물을 부수고 갈지 일일히 찾아서 min에다 저장하고 min과 cnt가 같으면 min_cnt를 하나씩 올려줬습니다.

2 - 1 이분 탐색을 통해 몇 개를 부숴야 하는지 찾았습니다. 예를 들면 정렬 된 석순 배열이 1 1 2 2 3 3 4 4 이고 2 높이에서 개똥벌레가 부수고 지나간다치면 2가 배열에서 인덱스가 얼마인지 찾고 그 다음에 2가 배열에서 처음 등장하는 인덱스를 찾았습니다. 그러면 2가 처음 나온 이후의 숫자들은 다 부수고 지나가야 하니까 cnt에 다 더해 줬습니다.

2 - 1 종유석 배열은 종유석의 길이를 배열에 넣은게 아니라 종유석 때문에 생기는 빈칸의 높이를 저장했기 때문에 1 1 2 2 3 3 4 4 같은 종유석 배열이 있고, 2 높이에서 지나가려면 역시 2를 찾고 2가 시작하는 인덱스를 찾아서 그 전까지 존재하는 숫자들의 개수를 cnt에 더해줬습니다. 2 높이에서는 빈칸을 1로 같은 종유석만 부수고 지나가야하니까요.

2 - 2 근데 1 1 3 3 4 4 같은 배열의 경우 2가 없으니까 2 높이에서 2를 찾을 수가 없어서 이분 탐색으로 -1을 출력하게 했고 -1이 나오면 높이를 1씩 증가시키면서 이분탐색을 하게 했습니다. 석순 같은경우 2 높이에서 부술 수 있는 장애물은 높이가 2 이상이면 되니까요. 

2 - 3 높이를 1씩 증가시키다가 h 높이까지 증가시켰지만 -1을 출력하면 석순의 경우에는 부술 장애물이 없다는 거고, 종유석의 경우는  다 부수고 가야한다는 뜻이기 때문에 그렇게 cnt를 처리했습니다.

시간초과가 왜 날까요 ㅠㅠ


game2k   7달 전

2 - 2, 2 - 3에서 시간초과 날것 같네요

2 500000

2

499999

답 1 499999

1 1 3 3 4 4 같은 배열의 경우 2가 없으면 2보다 작지 않은 첫번째는 3이라는 것을 바로 찾아야 합니다.

추천 검색어는 lower_bound

댓글을 작성하려면 로그인해야 합니다.