1. 문제 설명
수열의 합2N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.
10 5
1 2 3 4 2 5 3 1 1 2
2. 투 포인터 기법 적용
만약, 전체 해답을 모두 구한다면, 2중 for문을 돌려서 해결 할 수 있습니다. 모든 경우의 수를 봤을 때, O(N^2)만큼의 시간 복잡도가 걸리므로, 조건에서 fail이 되게 됩니다. 따라서, 위와 같은 문제는 특정 기법을 적용해야 되는데 여기서 사용되는 것이 바로 투포인터 기법입니다. start, end이렇게 2개의 포인터를 준비합니다. 그리고 다음과 같은 알고리즘 순서로 진행을 합니다.- end 포인터가 계속 늘려가면서 합의 값이 M이거나 보다 크게 되는 구간까지 늘립니다.
- 구간합이 M보다 작아지는 지점까지 start 포인터를 늘려 갑니다.
- 합의 구간이 M이 되는 경우 result값을 한개씩 증가합니다.
3. 투 포인터 그림 설명
위의 예시에 대해서 애니메이션으로 보시면 확실히 이해가 되실 것입니다. 아래의 그림이미지를 보면서 하나씩 정리해보겠습니다.
처음에는 위에 보이는것과 같이, start/end 포인터가 0지점을 가리키고 있습니다. 그리고 현재의 SUM값은 0 입니다.
end포인터를 우측으로 옮기면서 값을 하나씩 더해나갑니다. 구간합이 M(위의 예시에서는 5)과 같거나 커지는 지점까지 늘려나갑니다.
그리고 위의 그림과 같이 M값을 넘어가게 되면, start 포인터를 오른쪽으로 옮기면서 SUM값을 빼게 됩니다.
위의 그림과 같이 합이 M이 되는 구간을 찾고 result에 값을 한개 더하게 됩니다. 그리고 M과 같거나 커졌기 때문에 다시 start 포인터를 우측으로 옮깁니다.
위와 같은 방식으로 계속해서 start/end 2개의 포인터를 움직이면서 구간합이 M이 되는 것을 찾고 result를 추가해줍니다.
2번째 해답은 위와같습니다.
3번째 해답은 위와같습니다.
다시 start/end 포인터를 하나씩 옮기게 되면 위와 같고, end포인터는 끝까지 갔습니다. 더이상의 해답이 없기 때문에 start 포인터도 끝까지 우측으로 옮기게 되고, 해답을 찾습니다.
최종적으로는 답이 3개가 되고 while 문은 끝이 납니다.
4. 소스 코드
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N,K;
static int[] Arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Arr = new int[N + 1];
st = new StringTokenizer(br.readLine().trim());
for (int i = 0; i < N; i++) {
Arr[i] = Integer.parseInt(st.nextToken());
}
int i,j;
i = 0 ; j = 0;
int sum = 0;
int count = 0;
while(true){
if(sum >= K) sum -= Arr[i++];
else if(j == N) break;
else sum += Arr[j++];
if(sum == K) count++;
}
System.out.println(count);
}
}
while(true){
if(sum >= K) sum -= Arr[i++];
else if(j == N) break;
else sum += Arr[j++];
if(sum == K) count++;
}