1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
문제
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
출력
첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.
예제 입력 1
10 15
5 1 3 5 10 7 4 9 2 8
예제 출력 1
2
풀이 .
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = null;
static StringTokenizer st = null;
static int[] arr = null;
static int N, S, ans = 100001;
public static void twoPointer() {
int L = 0, R = 0;
int sum = arr[0];
while(R < N) {
if(sum < S) {
R += 1;
sum += arr[R];
}else if(sum >= S) {
ans = Math.min(ans, R - L + 1);
sum -= arr[L];
L += 1;
if(L > R) { // 사실 입력 부분에서 길이 1이 정답인 경우를 미리 체크했으니 이 조건문은 빠져도 상관 없다.
R = L;
sum = arr[L];
}
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
arr = new int[N + 1]; // R == N 됐을 때의 에러 방지
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
if(arr[i] >= S) {
System.out.println(1);
return;
}
}
twoPointer();
System.out.println(ans == 100001 ? 0 : ans);
}
}
2003번과 완전히 똑같은 투 포인터 문제.
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 1261 - 알고스팟 JAVA (0) | 2021.02.16 |
---|---|
[BOJ] 1644 - 소수의 연속합 JAVA (0) | 2021.02.16 |
[BOJ] 2003 - 수들의 합 2 JAVA (0) | 2021.02.15 |
[BOJ] 1182 - 부분수열의 합 JAVA (0) | 2021.02.15 |
[BOJ] 6603 - 로또 JAVA (0) | 2021.02.15 |