반응형
투포인터
-
BOJ) 수들의 합 2 (2003 번)알고리즘/백준 2021. 2. 18. 11:48
수들의 합 2 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net N개의 수열에서 i ~ j 번 째의 값들의 합이 M이 되는 경우를 구하는 문제다. N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) 의 조건이 주어진다. 투포인터는 슬라이딩 윈도우와 유사하지만 다른 점은 바로 탐색 구간의 길이가 정해져있지 않다는 것이다. 투포인터를 활용해서 푸는 문제인데, 익숙하지 않아서 기록에 남겨둔다. 우선, 시작점 탐색을 도와줄 left와 끝점 탐색을 도와줄 ..