[BOJ] 2003: 수들의 합 2

2003번: 수들의 합 2

 

풀이

 

배열 내에서 시작점과 끝나는 점을 옮겨주면서 합을 구해준다. (= 투포인터)

합 > M 일 경우에 start 점을 이동시키기 전에, 이전 arr[start]값을 빼줘야 했는데,

순서를 바꿔서 해놨더라 대체 어디서 안되는걸까 한참을 찾았는데 ..

 

3 1
1 2 1

답: 2

 

나는 위 테케를 해결했더니 문제가 해결 ..~!

반례라고 보기는 어렵지만 ㅎㅎ 테케가 더 많이 제공됐다면 좋았을 문제..

 

package 백준renew;

import java.io.*;
import java.util.*;

public class 실버4_2003_수들의합_2 {
	static int N, M, ans;
	static int arr[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		ans = 0;
		arr = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Check(0, 0);
		
		sb.append(ans);
		bw.write(sb.toString()); bw.flush(); bw.close();
		
	}
	static void Check(int start, int end) {
		int sum = arr[start];
		while(true) {
			if(end == N || start == N) {
				break;
			}
			if(sum < M) {
				end++;
				if(end == N) {
					break;
				}
				sum+=arr[end];
			}else if(sum > M) {
				sum-=arr[start];
				start++;
			}else {
				ans++;
				end++;
				if(end == N) {
					break;
				}
				sum+=arr[end];
			}
		}
	}
}