[BOJ] 1806 - 부분합

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/1806

1806번: 부분합

난이도: 골드 4

사용언어: JAVA

 

풀이

이 문제는 두 개의 포인터를 이용하여 해결할 수 있습니다. 수열에서 연속된 수들의 부분합 중에 그 합이 S를 넘는 것 중, 가장 짧은 것을 찾는 것이 문제이기 때문에, 연속된 수들의 첫 부분과 마지막 부분을 포인터로 가리키고, 이 두 포인터를 적절히 증가시키며 최소 길이를 구할 수 있습니다.

 

주어진 예제를 이용해 설명을 진행하겠습니다.

 

 

위의 값들을 배열에 담고, 두 개의 포인터를 준비해줍니다. 그 뒤에 아래와 같은 순서를 따릅니다.

 

 

 

 

위의 그림과 같이 두 개의 포인터를 이용해 결과를 result라는 배열에 담을 수 있고, 최종적으로 result에서 0을 제외한 가장 작은 값을 정답으로 출력시켜주면 됩니다.

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int i;
        int first = 0;
 
        s = br.readLine();
        st = new StringTokenizer(s);
        int[] arr = new int[N]; // 입력을 받는 배열
        int[] result = new int[N]; // 결괏값을 저장하는 배열
        int sum = 0, cnt = 0;
        for (i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i];
            if (arr[i] > S) { // 만일 한 숫자가 S보다 크다면 뒤는 더 볼 필요도 없이 정답은 1
                bw.write(String.valueOf('1'));
                bw.flush();
                System.exit(0);
            }
            cnt++;
            if (sum >= S) { // sum이 S보다 크다면,
                while (sum >= S) { //first를 한 칸씩 전진시키면서 S보다 큰지를 확인
                    sum -= arr[first++];
                    cnt--;
                }
                sum += arr[--first];
                cnt++;
                result[i] = cnt; // result 배열에 cnt 저장
            } else { // sum이 S보다 작다면,
                result[i] = 0; // 0 저장
            }
        }
 
       Arrays.sort(result); // 소팅을 수행해서,
        for (i = 0; i < N; i++) {
            if (result[i] != 0) { // result에서 0이 아닌 가장 작은 값 출력
                bw.write(String.valueOf(result[i]));
                bw.flush();
                System.exit(0);
            }
        }
        bw.write('0'); // S를 넘길 수 있는 조합이 없다면 0을 출력
        bw.flush();
    }
}