백준 11659번 (구간 합)

처음에는 제일 생각해내기 쉬운 반복문으로 짰다.

그럴 것 같았지만 시간초과 판정을 받았다. 아무래도 N과 M이 커지면 반복문을 너무 많이 돌리게 돼서 그런 것 같다.

새로운 방법으로 미리 0부터의 합을 더해놓는 리스트L2를 만들어놓고, i와j에 따라서 L2[j]-L2[i]를 구하면 미리 0부터의 합을 더해놓는 과정하나만 늘리면 그 이후의 반복문이 다 매우 간단해진다.

L = 5 4 3 2 1

L2 = 0 5 9 12 13 14

i = 1

j = 3

구간합 = L[0]+L[1]+L[2] = L2[j]-L2[i-1] = 12