prefix_sum 썸네일형 리스트형 BOJ 18830 - 하이퍼 수열과 하이퍼 쿼리 (D5) PS를 진짜 제대로 하겠다는 마음가짐으로 역겨운 것도 다 풀기로 했다. 하이퍼 시리즈는 유명하다... 차원이 말도 안되게 큰 문제들이다. 얘는 이 문제를 11차원으로 늘린 문제이다. 그럼 그냥 11차원 prefix sum을 박으면 되느냐? 아쉽게도 아니다. prefix sum table을 채우는 원리는 포함-배제 원리이다. 이는 중복하여 더하고 빼는 구간들을 처리하는 것이다. 그래서 11차원 prefix sum을 채우려고 식을 세워보면 무려 2^11(=2048)개의 값을 더하고 빼는 형태가 나온다. 그래서 table을 채우는데에는 총 O(2^11 * nmopqrstuvw)가 나와 전체 서브태스크를 풀 수 없다. (아마 섭태3까지는 풀릴 것 같다.) 다행히도 얘를 O(11 * nmopqrstuvw)에 채울.. 더보기 이전 1 다음