백준[2003] 수들의 합2

박지호·2022년 7월 5일
0

백준 2003 수들의 합2

Language

Java

INPUT

첫 번째 줄에는 주어지는 숫자 개수 N과 더해서 만들어야 하는 숫자 M이 주어진다.
두번째 줄에는 N개의 숫자 배열이 주어진다.

OUTPUT

연속한 일련의 숫자를 더하였을 때 M이 나오는 경우의 수를 출력한다.

문제 이해

상당히 간단한 설명의 문제이기에 아래 그림으로 일축한다.

Two Pointer

완전 탐색은 시간 소요가 크기 때문에 투 포인터를 사용해준다.

  1. ith 부터 시작하는 부분 수열을 더했을 때 M보다 작다면 ith 부터 시작하는 부분 수열을 확장해준다.
  2. ith 부터 시작하는 부분 수열을 더했을 때 M보다 더 커진다면 더 이상 그 수열을 확장할 필요가 없다.
  3. ith 부터 시작하는 부분 수열을 더했을 때 M과 같다면 확장 시켰을 경우 또 다시 M이 나올 수 없다. 따라서 ith 부터 시작하는 부분 수열은 더 이상 만들 필요가 없다. i+1 th 부터 시작하는 부분 수열을 탐색한다.

투포인터 작동 원리를 그림으로 표현하면 다음과 같다.

CODE

import java.io.*;


public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		//Input
		int N = Integer.parseInt(str.split(" ")[0]);
		long M = Integer.parseInt(str.split(" ")[1]);
		
		str = br.readLine(); // 다음 줄을 읽어준다.
		String[] array = str.split(" "); //배열을 담아준다.
		
		int start = 0; // start 포인터
		int end = 0; // end 포인터
		
		int[] arr = new int[N];
		
		for(int i = 0; i<N;i++) {
			arr[i] = Integer.parseInt(array[i]);
		}
		
		
		long sum = 0; // 합
		int result = 0; // 총 경우의 수
		
		while(start < N) { //start가 끝까지 훑을 때까지 

			if(sum >= M || end == N) { //만약 sum이 M보다 크거나 같으면
				sum -= arr[start]; //start 포인트가 앞으로 옮겨지므로 현재 point의 값은 수열에서 제외 --> sum에서 빼준다.
				start++;// start point를 앞으로 옮겨준다.
			}
			//만약 sum이 M보다 작다면
			else {
				sum += arr[end]; // end point를 더해준 후
				end++;// end point를 앞으로 옮겨준다.
			}
			
			//만약 합이 목표 합과 같다면 
			if (sum == M){
				result++; // 결과를 하나 더해준다.
				
			}
		}
		
		System.out.print(result);
		
	}

}

check

  • 처음 풀어본 투 포인터 문제! 투 포인터를 이해하기 쉬운 문제이다.
  • 메모리 초과 주의

0개의 댓글