https://www.acmicpc.net/problem/1806

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

코드설명

누적합과 투포인터를 활용하여 진행합니다.

 

문제로직입니다.

1. 먼저 누적합을 구해줍니다. ( 부분합 중에 그 합이 S 이상이 되는것을 구하기에 누적합을 구합니다. )

2. 누적합에서 투포인터를 활용하여 합 S보다 커질때까지 end 포인터를 계속해서 이동시킵니다. 

3. S보다 커졌다면, 부분합 중 S 이상이 되는 것 중 가장 짧은것의 길이를 갱신처리합니다.

4 .이제 start++ 처리를 통해 부분합의 크기를 줄여나갑니다.

5. 3번과 4번 과정을 계속진행합니다.

6. 계속해서 진행하다보면, start가 N보다 커지게 되고 종료됩니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, S;
public static int[] arr;
public static int[] prefixSum;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
arr = new int[N];
prefixSum = new int[N+1];
arr = new int[N];
int sumValue = 0;
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
arr[i] = Integer.parseInt(st.nextToken());
sumValue += arr[i];
prefixSum[i+1] = sumValue;
}
int start = 0;
int end = 0;
int sum = 0;
while(start < N) {
while(sum < S && end <= N) {
sum = prefixSum[end] - prefixSum[start];
end += 1;
}
if(sum >= S) { //만약 S가 sum보다 더 크거나 같다면, answer값과 길이를 비교해야합니다.
answer = Math.min(answer, end - start - 1); //end +=1 로 된 상태로 넘어오기에, -1 을 처리합니다.
}
sum -= arr[start];
start += 1;
}
if(answer == Integer.MAX_VALUE) {
System.out.println("0");
}else {
System.out.println(answer);
}
}
}

+ Recent posts