[C++] 백준 1806번: 부분합
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
골드4라기에는 난이도가 쉬운 편인 것 같다. 두 포인터라는 알고리즘 분류로 돼 있다. 나는 이름만 보고는 흔히 생각하는 start와 end를 0부터 N - 1까지 각각 훑는 O(N^2) 알고리즘인가 싶었다. 하지만 검색해서 알아보니 O(N) 알고리즘이었다.
https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0
[Algorithm] Two Pointers, 투 포인터
이번 포스팅에서는 Two Pointers 에 대해서 알아보도록 하겠습니다. Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘입니다. 여기서 두 개의 포인터를 사용하
ssungkang.tistory.com
end를 start부터 훑는게 아니라 구간 합이 S보다 작을 때까지 end를 증가하다가 S와 같거나 커지면 start를 늘리는 방식이었다. 생각해보니 end를 start부터 훑으면 구간 합이 작은 것부터 다시 계산하니 필요없는 연산량이 많아지는구나 깨달았다. 아무튼, 위에 소개된 방식으로 구현했더니 시간초과가 발생했는데, 이유는 쉽게 알 수 있었다. 0부터 i까지의 누적합을 구해두지 않아 중복 연산이 많아졌기 때문이다. 누적합까지 미리 계산해서 제출하니 쉽게 AC를 받을 수 있었다.
