<Algorithm> 21. 1806번 부분합

1. 1806번 부분합

• 주어진 배열을 순서대로 기준점을 두어 더했을때 기준 결과값 이상일 경우 그 기준점의 차이값의 최소값을 구하는 문제

• 주의할점은 2와 3일경우 길이는 2가 된다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static int min = Integer.MAX_VALUE;
    static boolean confirm = false;
    
    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[] input = new int[N];
        
        st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < N; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        
        partSum(input, S, 0, 0);
        
        if(confirm) {
            System.out.println(min);
        }else {
            System.out.println(0);
        }
        
    }
    
    private static void partSum(int[] input, int S, int left, int right) {
        
        int res = 0;
        if(right == input.length) return;
        
        for(int i = left; i <= right; i++) {
            res += input[i];
        }
        
        if(res <= S || ((left == right)&& res >= S) ) {
            
            if(res == S) {
                int len = right - left + 1;
                if(min > len) min = len;  // 최소값 변경
                confirm = true;
            }
            partSum(input, S, left, right + 1);
        }else if(res > S) {
            
            if(res >= S) {
                int len = right - left + 1; 
                if(min > len) min = len; // 최소값 변경
                confirm = true;
            }
            partSum(input, S, left + 1, right);
        }
            
    }
    
}