[코딩테스트 연습] 쿠키 구입

 

문제: https://programmers.co.kr/learn/courses/30/lessons/49995

---

1. N^2 탐색을 통해 모든 구간합 DP[L][R]을 구해줍니다.

 

2. 그리고 난 후 DP[L][M] == DP[M+1][R]인 구간의 갯수을 찾습니다.

이 때 M의 범위는 [L,R) 입니다. 이 범위 탐색을 이분 탐색을 통해 logN에 처리하면 N^2 logN으로 통과할 수 있습니다.

 

O(N^2)이 정해인 것 같은데, 문제를 해결한 아이디어만 얻어가시면 될 것 같습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter07.cc