https://programmers.co.kr/learn/courses/30/lessons/49995
-
flow
이 문제는 greedy 하거나 linear하게 풀 수 없을 것 같다고 느꼈다. 결국 A[l] 부터 A[m] 까지의 sum과 A[m+1] 부터 A[r] 까지의 sum 을 모두 비교해주는 작업이 최소 한번 씩은 들어가야 한다고 생각이 들었다. 이는 cookie size가 N일때 최소 시간복잡도 O(N^2) 가 됨을 의미하고 이 안에서 중복 계산 작업 없이 최적화를 목표로 했다.
처음에 생각한 방법은 s[i] 가 1부터 i까지의 cookie sum이라고 할 때, s[j] - s[i] = i부터 j까지의 구간합이 됨을 이용해서 구간 계산 중복을 피하자 생각했다.
그런데 그 다음에 루프를 어떤 식으로 하면 좋을 지 생각하다 보니 m을 1부터 N까지 반복해 나아가는데 m 에서 부터 좌측 sum 과 우측 sum 각각을 점차 늘려가면서 비교해 나아가면 위에서 생각했던 방법과는 별 상관 없이 필요한 계산만 해도 된다고 생각이 들었다. 처음 생각도 반영해서 코드를 짰지만 별 의미는 없어지게 되버렸다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level4/A49995.py
