백준 투포인터

[baekjoon 1806] 부분합 (투 포인터) (C++)

www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 시간제한이 0.5초로 매우 짧기 때문에, 부분합을 구하기 위해서 2중 for문을 돌면서 풀면 풀리겠지만 시간은 O(N^2)로 시간제한에 걸리게 된다. 따라서 이 문제는 O(N)의 시간 복잡도로 풀이가 가능한 두 포인터를 이용해야 한다. 두 포인터란 배열을 가리키는 포인터 인덱스 l, r (왼쪽, 오른쪽 맘대로)를 선언 후, 매번 조건과 비교하면서 왼쪽, 오른쪽 인덱스를 바꿔주며 배열을 탐색하는 것..