[백준 알고리즘] 1806번 자바(Java) 부분합

조건

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

풀이

반복문을 한번 돌려서 배열의 부분합을 이용해 답을 구해야하는 문제이다.
부분합 배열 값은 부분합, 길이, 시작점 ,끝점 4개의 정보가 있어야 한다.
만일 값이 해당 줄에 있는값을 초과하면 부분합의 길이를 minLen랑 비교해서

부분합의 길이가 더 낮으면 minLen = 해당부분합의 길이
그리고 다시 초과못하도록 첫위치부터 +해주면서 인덱스없애고
다시 S값 아래로 되면 새로운 값 추가하는식으로 진행한다

 

아래에 그림으로 부분합 과정을 표현해봤다

 

반복문 돌리기전

반복문을 돌려서 부분합에 값을 넣어준다

부분합이 24>=15가 되었다

부분합이 15미만이 될때까지 앞 index값들을 빼줬다

이렇게 빼준이후에 len는 지금 len에서 +1해줘야 아까 부분합 15가 넘는 길이가 되므로

1+1 해줘서 2가된다

위에 진행했던것처럼 반복

이렇게 쭉 반복해서 하면 최종적으로 min에 최소길이가 저장되는 코드다.

 

 

 

예제 입력 예시

10 15
5 1 3 5 10 7 4 9 2 8

 

예제 출력 예시

2

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//1806번 부분합

public class P1806 {
    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];

        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
        }

        int min = 100000;
        int[] partSum = new int[4];  //부분합, 길이, 시작점, 끝점
        for (int i = 0; i < N; i++) {
            partSum[0] += arr[i];  //부분합 추가
            partSum[1] ++;  //길이 1증가
            partSum[3] = i;  //끝점기록
            if(partSum[0]>=S){
                //부분합이 S보다 작아지도록 조정
                int startIndex = partSum[2];
                while(partSum[0]>= S){
                    partSum[0] -= arr[startIndex];
                    startIndex++;
                    partSum[1]--;
                    partSum[2]++;
                }
                //만족하는 부분합의 최소길이 구하기
                if(partSum[1] < min){
                    min = partSum[1]+1;
                }
            }
        }
        if(sum<S) min = 0;  //불가능할시 0출력
        System.out.println(min);
    }
}

 

 

 

 

문제 출처

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

1806번: 부분합