오답 여부: o
편집 시간: 2022년 4월 8일 오후 6:19
코드
Algorithm/1208.py at main · Junroot/Algorithm
풀이
평범하게 모든 수열의 경우의 수를 다 구하면 $2^{40}$이므로 시간 초과가 발생할 것이다. 처음에는 dp같은 방법으로 접근하였으나 중복되는 경우가 없기 때문에 효과가 없었다.
결국 답을 찾아봤는데, 수열을 절반으로 나누어 왼쪽과 오른쪽에서 나올 수 있는 합을 각각 따로 구하여 합이 될 수 있는 것을 찾으면 $2*2^{20}$이므로 제한 시간안에 해결할 수 있다.
시간 복잡도가 O($2^{n}$) 같이 제곱 수준일 때는 n의 크기를 절반으로 줄이는 것만(O($2^{{n \over 2}}$))으로도 큰 최적화가 될 수 있다는 것을 확인할 수 있었다.