백준 #백준 1806번 #부분합 #투포인터

www.acmicpc.net/problem/1806 투포인터를 이용해서 시간제한 안에 알고리즘을 작동시키는 것이 포인트입니다. 주어진 입력 N은 100,000 보다 작은 수 입니다. 모든 수열을 확인하는 방식은 O(N^2) 의 시간복잡도를 가지게 되는데 이는 문제의 시간제한 0.5초 안에 작동이 불가능합니다. 따라서 투포인터를 이용해서 시간 복잡도를 O(N)으로 구현했습니다. 우선 주어지는 N과 S 값, N개의 배열 원소를 입력 받습니다. int n, s; cin >> n >> s; for (int i = 0; i > arr[i]; } 이제 투포인터를 사용한 부분을 보겠습니다. int left = 0; int right = 0; int sum = arr[left]; int ..