[Java] 수들의 합2 [2003번]

https://www.acmicpc.net/problem/2003

• 예제 입력1

4 2
1 1 1 1

• 예제 출력1

3

• 예제 입력2

10 5
1 2 3 4 2 5 3 1 1 2

• 예제 출력2

3

---

• 문제 접근
  • 시간 제한 0.5초 ⇒ 5,000만번의 연산 이내로 해결
  • 첫째줄에 숫자의 개수 N과 i~j까지의 합이 M이 되어야하는 수가 주어짐
  • i ~ j까지 더하는데, i~j의 범위가 고정되어 있지 않음
    • 입력 예제 2의 예시
      • 1번째 경우의 수 ⇒ 2 3
      • 2번째 경우의 수 ⇒ 5
      • 3번째 경우의 수 ⇒ 3 1 1
• 문제 해결
  • 투 포인터 방식으로 문제 해결
  • 최초 start와 end를 같게 시작하여 다음의 규칙 만족
    • 목표값(M)보다 start~end의 합이 작을 경우 end 1증가
    • 목표값(M)보다 start~end의 합이 클 경우 start 1 증가
    • 목표값(M)과 start~end의 합이 같을 경우 start, end 둘 다 1증가

• 슈도 코드

N(수들의 개수 저장), M(목표값 저장)
count(경우의 수를 저장할 변수 선언)
A[] (수를 저장할 배열 선언)
for(N번 반복){
	A 배열에 값 저장
}
start, end (시작값, 끝값 저장)
while(end가 배열길이과 같지 않으면 반복){
	sum(누적합)
	for(i = start ~ end까지 반복){
		sum에 A[i] 누적
	}
	if(M보다 sum이 작다면) end 1증가
	else if(M보다 sum이 크다면) start 1증가
	else { // 같다면
		start 1증가
		end 1증가
		count 1증가
	}
}
count 출력

• 코딩하기

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken()); // 숫자의 개수
    int M = Integer.parseInt(st.nextToken()); // 목표값
    int matchCount = 0; // 경우의 수
    int[] A = new int[N];
    st = new StringTokenizer(br.readLine());
    for(int i = 0; i < N; i++){
        A[i] = Integer.parseInt(st.nextToken());
    }
    int start = 0, end = 0; // 투 포인터로 사용될 시작, 끝 변수
    while(end != A.length){ // end가 배열의 길이와 같아지면 종료
        int sum = 0;
        for(int i = start; i <= end; i++){
            sum += A[i];
        }
        if(M > sum) // 목표값이 더 크다면, end 인덱스를 늘려 sum의 값을 높임
            end++;
        else if(M < sum) // 목표값이 더 작다면, start 인덱스를 1 늘려 sum의 값을 줄임
            start++;
        else{ // 목표값과 sum이 같다면, 경우의 수를 카운팅하고 start와 end를 1씩 늘림
            start++; end++; matchCount++;
        }
    }
    System.out.println(matchCount);
}