안녕하세요.
이 문제의 시간복잡도를 통과하려면 이분탐색을 이용해 전처리과정이 필요합니다.
우선 예제1번의 배열을 정렬해두면,
20 7 5 2
3 7 9 9 12 14 15
가 됩니다. 이때 cnt[]배열을 선언해두어 각 위치에서 차를 마셨을때 효과가 적용되는 음식의 개수를 전처리 해두어야 합니다. 그렇다면 cnt배열은
2 3 3 2 3 2 1
이 되고, 이때 전처리과정을 이분탐색을 이용하면 O(NlogT)에 완료할 수 있습니다.
전처리과정이 끝나고, dp테이블을 [idx][마실 수 있는 차의 개수]로 선언하여 문제를 풀 수 있습니다.
cherub8128 3년 전
시간을 순차적으로 늘려가는 식으로 동적계획법을 쓰면 짧은 간격일 때는 괜찮은데
간격이 길어지면 시간, 메모리 초과가 될 수 밖에 없더라고요...
이분 탐색을 어떤식으로 적용하는지 감이 안옵니다ㅠㅠ 유사한 문제도 찾기가 어렵네요...
푸신 분들 계시면 힌트 주시면 감사하겠습니다.