[BOJ 2003] 수들의 합2 (Java)

BOJ 2003 수들의 합2

문제풀이

짧은 시간 제한과 M의 엄청난 범위에 겁을 먹어서 고민을 많이 했지만 2중 반복문의 형태로 단순히 풀었더니 통과해버렸다. 하지만 이 문제는 알아보니 투 포인터를 사용하는 문제였다. 두 개의 포인터가 각자의 조건에 따라 움직이는 형태다.

• start는 합계가 M과 같거나 커질때 까지 계속 증가한다.
• end는 합계가 M과 같거나 작아질때 까지 계속 감소한다.
• 양쪽 끝의 포인터가 각자의 조건에 따라 증가하며 문제에서 요구하는 조건을 충족시킨다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int[] numbers;
	static int N, M, ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		ans = 0;
		numbers = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N ; ++i) {
			numbers[i] = stoi(st.nextToken());
		}
		
		// 투 포인터가 될 start, end
		int end = 0;
		int sum = 0;
		
		for(int start = 0 ; start < N ; ++start) {
			// start를 증가시키며 sum에 더 한다.
			sum += numbers[start];
			
			// sum이 정확히 M이 되면 
			if(sum == M) {
				ans++;
				// ans를 증가시키고 현재 end위치의 수를 sum에 빼주고 end를 증가시킨다.
				sum -= numbers[end++];
			} else if(sum > M) {
				// sum이 M을 넘었을 
				while(sum > M) {
					// sum이 M보다 작아지거나 M과 같아질 때 까지 반복하며
					// end를 증가시키며 가 가리키는 수를 sum에서 뺀다. 
					sum -= numbers[end++];
					
					if(sum == M) {
						ans++;
						break;
					}
				}
			}
		}
		
		System.out.println(ans);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

투포인터를 사용하는 문제

• BOJ 1806 부분합
• BOJ 1644 소수의 연속합
• BOJ 2143 두 배열의 합