[백준] 30621 어? 금지 (C++)

어? 금지 문제 풀이

[백준] 30621 어? 금지

문제

조건

1. 성우는 주어진 시각 중 일부를 선택해 “어?“를 외칠 수 있음.
2. 시각 \(t_i\) 에서 외치려면 이전 \(b_i\) 시간 동안 다른 “어?“가 없어야 함.
3. 선택한 시각들의 총 혼란도 \(c_i\) 합을 최대로 만들어야 함.

풀이 방식

이번 문제는 dp를 활용하는 문제였다. 그러나 전체 시간을 기준으로 탐색하는 것이 아니라 입력받은 시간 배열을 활용해서 문제 풀이하는 것이 중점이였다.
전체 시간의 범위가 1,000,000,000 이기 때문에 모든 배열을 순회하는 것은 시간 초과가 날 수 있다고 생각했다. 그러나 내가 문제 풀이시에 오래 걸렸던 부분이 \(t_i - b_i\) 이면서 가장 큰 index를 찾을 때 내림 차순으로 순회하는 방식으로 풀이했는데 그렇게 하다 보니 시간 복잡도가 이진 탐색을 통해 풀이하는 것보다 오래걸린다는 것을 알 수 있었다.
마지막으로 생각 못했던 부분은 dp, 메모제이션을 활용하는 배열의 type을 int로 작성했다는 부분이였다. 혼란의 하나의 크키가 \(10^9\) 인 만큼 최댓값을 찾다보면 overflow의 가능성을 생각하지 못했다. 그래서 타입을 long long으로 수정한 후에 정답을 얻을 수 있었다.

답안

참고자료

백준 어? 금지 풀러가기