BOJ - 1806 ) 부분합
https://www.acmicpc.net/problem/1806
1806번: 부분합
문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길
www.acmicpc.net
역시 이어서 투포인터 유형1번문제이다.
https://algorithmstudy-mju.tistory.com/120
BOJ - 2003 ) 수들의 합 2
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각..
algorithmstudy-mju.tistory.com
위에 유형을 좀 정리해놓았다.
배열의 처음에 시작하여 목표숫자가 넘으면 개수를 세고, 그때의 s번째의 숫자를 빼준다.
다음 루프에서 목표숫자보다 작다면, e번째숫자를 더해준다.
위 작업을 반복하고, e가 맨마지막에서 목표숫자보다 클경우, 작을때까지 계속 빼주면서
사용된 숫자개수중 최소를 찾아간다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int t = Integer.parseInt(st.nextToken());
int num[] = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < n ; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
int sum = num[0];
int cnt = 1;
int answer = 100001;
for(int s=0,e=0 ;;) {
if(sum < t) {
e++;
if(e==n) break;
cnt++;
sum+=num[e];
} else if(sum >= t ) {
answer = answer > cnt ? cnt : answer;
cnt--;
sum-=num[s];
s++;
if(e==n-1) {
while(sum>=t) {
answer = answer > cnt ? cnt : answer;
cnt--;
sum-=num[s];
s++;
}
}
}
}
System.out.println((answer = answer ==100001 ? 0 : answer ));
}
}