문제링크 https://programmers.co.kr/learn/courses/30/lessons/92344 무지성으로 풀면 무조건 시간초과난다 이 문제는 정확성과 효율성이 따로 구분되어있다. 무조건 모든 방식에서 생각해봐야한다는거다 시간초과 코드는 하단에 첨부한다 사전지식 : 누적합 보통 구간의 합계를 sum(리스트시작:리스트끝) 이걸로 구하는데 이게 리스트길이만큼의 시간복잡도가 사용된다. 그러면 합산 한번당 O(n)이 걸리는데 당연히 연산 횟수가 많아지면 많아질수록 비례해서 길어질것이다 그런데 누적합을 사용한 방식은 누적합계를 더한다음에 리스트끝원소-리스트시작원소 를 지정해서 계산하는데 리스트인덱싱1개는 O(1)이거든요. 그래서 누적합은 O(1)+O(1) 시간에 구간의 합계를 구할수 있어서 사용한다..