https://www.acmicpc.net/problem/1806
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
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());
}
int sum = 0, left = 0, cnt = 0, answer = Integer.MAX_VALUE;
boolean exist = false;
for(int right = 0; right<n; right++){
sum+=arr[right]; // right 인덱스를 증가시키며 sum에 누적
cnt++;
while(sum >= s) { // 합이 s이상이면
exist = true;
answer = Math.min(answer, cnt); // 최소 길이 갱신
sum -= arr[left++]; // left 인덱스를 증가시키며 그 값을 빼줌
cnt--;
}
}
System.out.println(exist ? answer : 0);
}
}
n의 범위가 10만이므로 O(n^)으로 풀면 안된다.
투포인터 알고리즘을 사용해 O(n)으로 줄이도록 한다.
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 2003번- 수들의 합 (0) | 2023.01.31 |
---|---|
[JAVA] 백준 1644 - 소수의 연속합 (0) | 2023.01.26 |
[JAVA] 백준 11657- 타임머신(벨만 포드) (0) | 2023.01.23 |
[JAVA] 백준 1541- 잃어버린 괄호 (0) | 2023.01.21 |
[JAVA] 백준 11404번- 플로이드 (0) | 2023.01.20 |