[BOJ #11659] 구간 합 구하기 4 BOJ #11659, 구간 합 구하기 4 문제입니다. 원소 수 N개의 정수 배열이 주어졌을 때 입력된 구간의 합을 출력하면 됩니다. 프로그램 자체가 간단하지만, 일반적인 방법으로는 시간복잡도가 너무 높아 시간 내에 풀 수 없습니다. 이를 해결하기 위해서는 '누적합'을 이용하면 됩니다. 수학에서 수열을 다룰 때 급수를 이용해 a_n = s_n - s_(n - 1)과 같이 나타내는 것과 동일한 원리를 이용합니다. 이것을 알면 코드 구현은 어렵지 않게 할 수 있겠습니다! 추가적으로 더 효율적인 방식도 있고 다양한 방식이 있으니 검색을 통해 찾아보시거나 직접 떠올려 보시면 큰 도움이 될 것이라고 생각합니다. 간단한 코드이나 제 코드를 첨부하도록 하겠습니다. 더보기 #include #include int main.. 2020. 7. 19. 이전 1 다음