https://www.acmicpc.net/problem/2003
문제
> N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다.
> 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가
M이 되는 경우의 수를 구하는 프로그램을 작성하시오.접근
주어진 배열 A에 대해 누적합을 구해둔다.
맨 마지막 인덱스의 누적합을 right, 맨 마지막 -1 번째를 left로 두고 right에서 left를 빼나간다.
뺀 값이 M보다 작으면 left를 0번 인덱스에 가까워지도록 -1씩 해주고, M보다 크거나 같을 땐 right를 -1해준다.
이 때, M과 같다면 경우의 수를 누적해준다.
문제해결
> 수열의 원소 수 N과 원하는 누적합M을 입력받는다.
> num배열에 수열을 입력받고, sum배열에 누적합을 구해 저장한다.
> left를 sum배열의 size-2로 뒤에서 두번째 원소를 가리키고,
right를 size-1로 마지막 원소를 가리킨다.
> while문으로 left가 음수, 배열의 범위를 벗어날 때까지 반복하며 rst에 경우의 수를 누적한다.
> right, left인덱스에 있는 누적합의 차이가 M보다 작으면 left를 왼쪽으로 민다.
> 크거나 같으면 right를 왼쪽으로 미는데 같을 땐 경우의 수를 누적한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2003번 수들의 합2
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] sum = new int[N+1];
int[] num = new int[N+1];
sum[0] = num[0] = 0;
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) {
num[i] = Integer.parseInt(st.nextToken());
sum[i] = sum[i-1] + num[i];
}
int left = sum.length-2;
int right = sum.length-1;
int rst = 0;
while(left >= 0) {
int diff = sum[right] - sum[left];
if(diff < M) {
left--;
continue;
}
if(diff == M) rst++;
right--;
}
System.out.print(rst);
}
}
후기
누적합을 구해서 두 포인터로 뒤에서부터 따져줬지만 누적합을 사용하지않고 두 포인터만으로 num배열의 첫 인덱스부터 시작해서 합이 M보다 작다면 right를 계속 증가시킨다.
그러다 M보다 커지거나 같아지면 left를 증가시키며
즉석에서 합을 계산해나가는 방법이 있었다.
