[백준 2003] (투 포인터) 수들의 합 2 (자바)

백준 2003번 수들의 합 2 (자바)

 

 

 

출처

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

 

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

 

 

출력

첫째 줄에 경우의 수를 출력한다.

 

 

 

 

입출력 예

입출력 예 1

 

 

 

걸린 시간

책을 보면서 공부했던 로직을 그대로 사용해서 5분..!

 

 

 

접근 방법

그저께 투포인터 공부하면서 처음에 풀었던 문제다.주어진 배열에서 정해진 크기의 연속된 합을 구해야 하는데 시작(start)과 끝(end)을 갱신하면서 구간합을 구하면 된다.

 

투포인터 알고리즘의 흥미로운 부분은 구간 배열의 길이를 start가 아니라 end를 1칸씩 뒤로 이동시키면서 합을 구하는 것이다.따라서, for문 사용 시 각 start마다 end를 계속해서 증가시키면서 구간을 구한다.

 

이 문제는 구간합이 m이 되는 경우의 수를 찾는다.합을 계산할 변수(intervalSum)가 m보다 작고 end가 n보다 작은 경우 배열의 두 번째 원소를 계속 더해주고 end+1씩 하여 구간을 늘린다.합이 m과 같으면 카운트를 증가시키고 다음 구간을 시작해야하기 때문에 사용하지 않을 start번째 원소를 빼준다.

 

 

 

내 코드

 

 

 

고려할 점

1. 투 포인터 알고리즘의 정석 문제

2. end를 사용하며 구간을 늘릴 것