백준 12892 파이썬 문제

https://www.acmicpc.net/problem/12892

12892번: 생일 선물

 

1. N = 100,000이고 완전탐색을 할 경우 10억의 시간이 필요하다. 따라서 TLE 발생한다.
2. N^2에서 시간을 줄여야 할 필요가 있다. 가능한 경우의 수는 그리디, DP, 이분탐색, 두 포인터다.
3. 정렬하게 되면, 가장 큰 값을 가지는 영역을 구하면 되는 문제로 치환이 가능하다.
4. 항상 모든 값은 양수이기 때문에 영역의 길이가 가장 긴 놈들 중에 가장 큰 값을 가지는 것으로 치환이 가능하다.
5. 따라서 두 포인터 문제로 치환할 수 있다.
6. 이 때, R의 값이 커질 때만 정답인지를 체크하면 된다. 왜냐하면 L의 값이 커지면, 범위가 작아지기 때문에 항상 지금보다 더 작은 값이 되기 때문이다.
7. R > 배열 길이보다 클 때까지 체크를 반드시 해야한다. 왜냐하면 가장 마지막에 있는 R만 있을 때가 가장 큰 값을 가질 수 있기 때문이다. L > R인 경우가 되면 체크하지 않아도 된다. 왜냐하면 L = R인 경우가 값의 차이가 가장 적어지는 것이기 때문에 L > R인 경우는 있을 수 없기 때문이다. (문제에서 주어진 값은 D >= 1이다)

https://github.com/chickenchickenlove/BOJ-Algorithm/tree/main/BOJ_%EB%B0%B1%EC%A4%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98