백준 문제풀이
[백준 1806] - 부분합(JAVA)
쿠쿠s
2021. 12. 31. 16:33
[문제]
-출처 https://www.acmicpc.net/problem/1806
[문제 풀이]
[백준 2003번 수들의 합2] 문제와 매우 유사한 문제이다. -> 해당 풀이
연속된 수들의 부분합 중에 그 합이 S 이상 되는 것중 가장 짧은 것의 길이를 구하는 문제이다.
연속된 수이고 자연수로 이루어져있으니 투 포인터를 이용하여 쉽게 해결 할 수 있는 문제이다.
두가지 조건만 잘 지키면 된다.
- 합이 S 이상
- 가장 짧은 것의 길이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
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 a[] = new int[n+1];
st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) {
a[i] = Integer.parseInt(st.nextToken());
}
int sum=0;
int left=0;
int right=0;
int ans = Integer.MAX_VALUE;
int leng =0;
while(right <= n) {
if(sum >= s) { // 합이 s 이상!
sum -= a[left++];
leng = right - left + 1; // 길이를 구하기
if(ans > leng) ans = leng; // 길이의 최솟값
}else if(sum < s) {
sum += a[right++];
}
}
System.out.println((ans) == Integer.MAX_VALUE ? 0 : ans);
}
}