[백준 1806] 부분합 / 자바 / 투포인터 && 누적합

문제         

레벨: G4
알고리즘: 투포인터 && 누적합
풀이시간: 1시간
힌트 참조 유무: 유

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

1 번째 시도   

 

입력값을 보면 O(NS)의 시간복잡도는 안 된다는 것을 알 수 있다.

그렇다면 가능성 있어 보이는 건 최대 O(NlogN) 정도이다.(일종의 꼼수) 여기서 얻을 수 있는 점은 배열을 1 ~2번 순회(적은 순회라고 생각하면 됨)정도로 답을 구해야 한다.

 

[아이디어]

나는 한 번의 배열 순회로 알아낼 수 없을까 라는 생각에서 출발했다.

배열을 전부 순회할 때까지 이 과정을 반복한다.

1. 15이하라면 다음 숫자를 합에 포함시킨다.

2. 15이고 기존 값보다 작다면 값을 갱신한다.

3. 15이상이라면 시작숫자를 합에서 제외시키고 시작숫자+1을 시작숫자로 삼는다.

 

[구현 어려움]

투포인터가 움직이기 못할 때 종료해야 하는데, 그걸 구현하기 힘들었다.

[해결법] 

배열을 N크기가 아닌 N+1로 만든다. 

종료조건은 end나 start가 N+1 이상이 될 때이다.

import java.util.*;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int s = scan.nextInt();
        
        int[] nums = new int[n + 1];
        for(int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        
        int min = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int total = 0;
        while(start <= n && end <= n) {
            if(total >= s && min > end - start) min = end - start;
            
            if(total < s) total += nums[end++];
            else total -= nums[start++];
        }
        
        if(min == Integer.MAX_VALUE) System.out.println("0");
        else System.out.println(min);
    }
}