알고리즘/백준
[JAVA]백준_1806_부분합
박 현 황
2021. 4. 14. 11:43
문제링크
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
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 arr[] = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) arr[i] = Integer.parseInt(st.nextToken());
// System.out.println(Arrays.toString(arr));
int start = 0;
int end = 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
while(true) {
if(sum >=S) {
minLen = Math.min(minLen, end-start);
sum -= arr[start++];
}
else if(end == N) break;
else if(sum <S) {
sum +=arr[end++];
}
}
System.out.println(minLen<Integer.MAX_VALUE?minLen : "0");
}
}
for문 두개 돌려서 사용하면 시간초과가 뜬다.
따라서 투 포인터 사용해서 해결해야하는 문제다.
일차원 배열에서 start와 end 인덱스를 통해 해결하면된다.