백준 풀이 : 1806 부분합

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int[] list = new int[n];
		int[] sumList = new int[n+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		
		sumList[1] = list[0];
		for(int i=2; i<n+1; i++) {
			sumList[i] = list[i-1] + sumList[i-1];
		}
		
		int min = n+1;
		
		for(int i=0; i<n+1; i++) {
			int l = i+1;
			while(l < n+1) {
				if(sumList[l] - sumList[i] >= s) {
					if(min > l-i) {
						min = l-i;
					}
					break;
				}else {
					l += 1;
				}
			}
		}
		
		if(min == n+1) {
			System.out.println(0);
		}else {
			System.out.println(min);
		}
		
	}

}

이 문제는 투포인터를 공부하기 위해 풀었다.

투포인터는 무조건 정렬이 되어있어야 사용할 수 있기 때문에 어떻게 정렬을 할 수 있을지 생각했다.

 

부분합은 누적합 수열을 생각하면 오름차순 정렬이 된 수열을 얻을 수 있다.

또 하나의 중요한 점은 누적합 수열을 바로 0항부터 시작하면 0항의 값을 차를 이용해 구할 수 없다.

예를 들어 주어진 수열이 10, 1, 2, 3 이라면 누적합 수열을 10, 11, 13, 16 으로 만들면 두 항의 차로 계산했을 때 맨 앞의 항인 10을 사용할 수 없다. 따라서 누적합 수열은 0부터 시작해야한다.

 

다음은 정답코드이다.