백준 2003번 수들의 합2

팀과제

문제 출처 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이 되는 경우의 수를 구하는 프로그램을 작성하시오.

⇒ 수열의 연속적인 부분에서 부분합이 m이 되는 경우의 수를 구한다.

입력

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

⇒ n은 수열의 항 개수(=배열 크기), m은 부분합과 같아야 하는 수

수열의 각 수들은 자연수 

출력

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

⇒ 부분합이 m이 되는 경우의 수를 세서 출력

예제 입력 1

4 2
1 1 1 1

예제 출력 1

3

예제 입력 2

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

예제 출력 2

3

---

풀이

• 부분합의 시작 인덱스와 끝 인덱스를 가리킬 포인터 2개가 필요하다.
• 부분합과 m을 비교
  1. 부분합 >= m
     1. 부분합 == m 이면 카운터 1 올린다,
     2. 끝 포인터를 옮기면 부분합이 커지니 시작 포인터를 옮긴다.)
        1. 시작 포인터를 옮기기 전에 부분합에서 현재 시작 포인터가 가리키는 수를 뺀다.
        2. 시작 포인터를 옮긴다.
  2. 부분합 < m
     1. 끝 포인터를 옮긴다. (부분합을 더 크게 만들기 위해)
     2. 끝 포인터를 옮기고 나서 부분합에 끝 포인터가 가리키는 수를 더한다.
• while 반복 조건을 모르겠음

import java.util.*;

public class Main {

	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();
		int m = scan.nextInt(); 
		// 수열의 s번째 수부터 e번째 수까지의 누적합이 m이 되어야 한다.

		int[] arr = new int[n];	// n개의 수로 된 수열
		for (int i = 0; i < arr.length; i++) { // 수열 입력
			arr[i] = scan.nextInt();
		}

		int count = 0;	// 경우의 수. 출력할 결과
		//-----------------------------------------------------------------------------
		int s = 0; 		// 시작 포인터 인덱스
		int e = 0; 		// 끝 포인터 인덱스
		int sum = arr[s];		// 부분합

		// 반복문 while 반복 조건??? 
		for(int i = 0; i < 10; i++) {
		//while(e<n-1) {
			//System.out.printf("start=%d, end=%d, sum=%d\\n", s, e, sum);
			
			if (sum >= m) {			// 부분합이 m보다 크거나 같으면 
				if (sum == m) {		// 부분합이 m과 같으면 카운트 올린다.
					count++;
				}									
				
				sum -= arr[s];		// 누적합에서 시작 포인터가 가리키는 수를 빼고
				s++;							// 시작 포인터를 옮긴다.

			}else {						// 부분합이 m보다 작으면
				
				e++;						// 끝 포인터를 옮긴다.
				sum += arr[e];	// 부분합에 끝 포인터가 가리키는 수를 더한다.
			}
			
			//System.out.println("count="+count);
		}
		//------------------------------------------------------------------------------
		System.out.println(count);

	}

}

 

• 그냥 무한반복으로 하고 탈출 조건을 넣었다.
• 부분합이 m보다 크거나 같으면 -> 시작 포인터를 옮겨야 하는데 시작 포인터가 지금 인덱스 끝이라면 갈 데가 없으니까 반복 종료
• 부분합이 m보다 작으면 -> 끝 포인터를 옮겨야 하는데 더 갈 데가 없으면 반복 종료

import java.util.*;

public class Main {

	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);

		int n = scan.nextInt();	// 배열 크기
		int m = scan.nextInt(); // 부분합과 비교할 수

		int[] arr = new int[n];	
		for (int i = 0; i < arr.length; i++) { // 배열 입력
			arr[i] = scan.nextInt();
		}

		int count = 0;	// 경우의 수. 출력할 결과
		//------------------------------------------------------------------------------
		int s = 0; 		// 시작 포인터 인덱스
		int e = 0; 		// 끝 포인터 인덱스
		int sum = arr[s];		// 부분합

		while(true) {
//			System.out.printf("start=%d, end=%d, sum=%d\\n", s, e, sum);
			
			if (sum >= m) {			// 부분합이 m보다 크거나 같으면 
				if (sum == m) count++;		// 부분합이 m과 같으면 카운트 올린다.
					
				if(s == n-1) break;	// 시작 포인터가 끝에 닿으면 반복 종료
				// 부분합이 m보다 크거나 같으면 시작 포인터를 옮겨야 하는데 갈 데가 없으니까 반복 종료
				
				sum -= arr[s];		// 누적합에서 시작 포인터가 가리키는 수를 빼고
				s++;							// 시작 포인터를 옮긴다.

			}else {						// 부분합이 m보다 작으면
				
				if(e == n-1) break; // 끝 포인터가 끝에 닿으면 반복 종료
				// 부분합이 m보다 작으면 끝 포인터를 옮겨야 하는데 더 갈 데가 없으면 반복 종료
				
				e++;						// 끝 포인터를 옮긴다.
				sum += arr[e];	// 부분합에 끝 포인터가 가리키는 수를 더한다.
				
			}
			
//			System.out.println("count="+count);
		}
		//------------------------------------------------------------------------------
		System.out.println(count);

	}

}

• 주석 떼고 돌린 결과

10 5
1 2 3 4 2 5 3 1 1 2 // 입력
start=0, end=0, sum=1 // 주석 부분
count=0
start=0, end=1, sum=3
count=0
start=0, end=2, sum=6
count=0
start=1, end=2, sum=5
count=1
start=2, end=2, sum=3
count=1
start=2, end=3, sum=7
count=1
start=3, end=3, sum=4
count=1
start=3, end=4, sum=6
count=1
start=4, end=4, sum=2
count=1
start=4, end=5, sum=7
count=1
start=5, end=5, sum=5
count=2
start=6, end=5, sum=0
count=2
start=6, end=6, sum=3
count=2
start=6, end=7, sum=4
count=2
start=6, end=8, sum=5
count=3
start=7, end=8, sum=2
count=3
start=7, end=9, sum=4
3 // 출력

 

Reference

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)