백준 1806. 부분합

tose33 2022. 3. 2. 15:47

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

투 포인터 알고리즘으로 합이 s이상이면 합을 감소시키기 위해 left 포인터를 오른쪽으로,

s 미만이라면 합을 증가시키기 위해 right를 오른쪽으로 이동하면 된다.

투 포인터 알고리즘에선 항상 포인터를 이동시키고 합을 증감시킬지, 증감 시키고 포인터를 이동할지를 조심해야한다.