글 읽기 - 풀이 관련 질문있습니다.

(追記) (追記ここまで)

1208번 - 부분수열의 합 2

원래라면 최대 2^40 으로 모든 부분 수열의 합을 구해서 S가 되는 개수를 구해줘야 되는데

이걸 반으로 나눠서 2^20 두 번의 합으로 S가 되는 개수를 구할 수 있다는 점이 어떻게 가능한지 궁금합니다.

뭔가 당연한거 같은데 수학적으로 어떻게 증명이 되는지 궁금합니다.

2^40의 메모리 대신 2^20 * 2로 메모리를 줄일 수 있고

시간 측면에서도 전체 2^40 경우의 수를 탐색하는 대신

2^20 개 씩으로 나누어 정렬된 상태로 저장한뒤 이분탐색을 사용하면 O(2^20 * log(2^20)) 으로 해결 가능합니다.

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge