[JAVA]BOJ 1806, 부분합

예전에 비슷한 문제를 풀었던 것 같아서.. 그렇게 하다가 틀렸습니다 받고 투포인터로 다시 풀었다 ㅎㅎ.. 사실 바로 떠오르긴 했는데 확신이 안서서.. 암튼 풀어봅시다.

 

처음에 생각한 방법

처음부터 더한다. 더하다가 S보다 커지면 앞에서 하나씩 뺀다. 그때 count를 비교해서 최소를 저장한다.. 가 되겠다.

 

public static int twoPointerSubTotal(int[] sequence, int S){
    int i = 0, j, min = 100000001;
    long sum = 0;

    for(j=0;j<sequence.length;j++){
        sum += sequence[j];
        while(sum >= S){
            min = Math.min((j - i + 1), min);
            sum -= sequence[i];
            i++;
        }
    }

    return (min == 100000001) ? 0 : min;
}

j가 실제로 더하는 인덱스이고, i는 sum >= S 일때 앞에서부터 순차적으로 빼는 역할을 한다. 순차적으로 빼야하니까 while문을 실행하고, sequence[i]를 빼고나면 i를 증가시켜준다.

예외처리가 있다. 이 문제는 S보다 크거나 같은 부분합 중에 개수가 적은걸 출력한다. 딱 같아야 하는게 아니다.

3 5
2 3 10
답 : 1 -> '10 >= 5'이기 때문에..

2 3
1 3
답 : 1 -> '3 >= 3'

3 3
1 1 1 
답 : 3

3 5
1 1 1
답 : 0 -> '전체 수열의 합 < S'

반례는 이정도.. 신경쓰면 된다.

전체 수열의 합이 S보다 작은경우를 계산하기 위해 min을 100,000,001 으로 정했다.(최대 S값이 100,000,000 이라서)

 

---

아래는 전체 코드이다.

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

public class BOJ1806 {
    public static int twoPointerSubTotal(int[] sequence, int S){
        int i = 0, j, min = 100000001;
        long sum = 0;

        for(j=0;j<sequence.length;j++){
            sum += sequence[j];
            while(sum >= S){
                min = Math.min((j - i + 1), min);
                sum -= sequence[i];
                i++;
            }
        }

        return (min == 100000001) ? 0 : min;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, S, i;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        int[] sequence = new int[N];

        st = new StringTokenizer(br.readLine());
        for(i=0;i<N;i++)
            sequence[i] = Integer.parseInt(st.nextToken());

        System.out.println(twoPointerSubTotal(sequence, S));
    }
}