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); } } }
'알고리즘 > Prefix_Sum' 카테고리의 다른 글
[백준] 11659 구간 합 구하기 4 - 누적합(Prefix Sum) JAVA (0) | 2023.08.13 |
---|---|
[백준] 10986 나머지 합- 누적합(Prefix Sum) + 수학(나머지) JAVA (0) | 2023.08.13 |
[백준] 21921 블로그 - 누적합(Prefix Sum) + 슬라이딩 윈도우(Sliding Window) JAVA (0) | 2023.08.06 |
[백준] 11660 구간 합 구하기 5 - 누적합(2차원, (Prefix Sum)) JAVA (0) | 2023.07.25 |
[백준] 2167 2차원 배열의 합 - 2차원 누적합(Prefix Sum) JAVA (0) | 2023.07.24 |