백준 알고리즘 11659번(구간합 구하기)

♣ 문제

 

 

♣ 문제 풀이 아이디어

이 문제는 리스트의 구간합을 구하는 문제이다. 반복문을 이용해서 특정 구간의 합을 구할 수도 있지만 시간이 오래 걸린다. 구간합 문제는 첫 번째 숫자부터 특정 숫자를 더한 값을 이용하여 해결할 수 있다 .

 

위의 예시의 경우

5  4  3  2  1  

 

주어진 수를 하나씩 더해서 요소를 구성하면

0  5  9  12  14  15  이다. 

 

첫 번째 숫자 0은 아무것도 더하지 않았을 때, 5는 첫 번째 수인 5만 더했을 때, 두 번째 수인 9는 5와 4를 더했을 때... 이런 식으로 구성된다. 

 

0 = 수를 더하기 전

5 = 첫 번째 수

9 = 첫 번째 수 + 두 번째 수

12 = 첫 번째 수 + 두 번째 수 + 세 번째 수

14 = 첫 번째 수 + 두 번째 수 + 세 번째 수 + 네 번째 수

15 = 첫 번째 수 + 두 번째 수 + 세 번째 수 + 네 번째 수 + 마지막 수

 

구간합을 구할 때, 예를 들어 2번부터 5번까지의 수를 더한 합을 구하라고 하면

( 첫 번째 수 + 두 번째 수 + 세 번째 수 + 네 번째 수 + 마지막 수) - (첫 번째 수) 를 계산하면 된다. 

 

따라서 0, 5, 9, 12, 14, 15를 리스트에 넣은 후, 구간 i부터 j까지 더한 합을 구하라고 하면 list[j - list[i-1] 을 계산하면 된다. 

 

정답 코드