[백준] 1806: 부분합 (누적합, 투포인터) - JAVA

알고리즘 분류 - 두 포인터

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

 

 

 

# 문제

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

 

# 예제

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

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

 

 

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

2

 

# 필요개념

이 문제에서 신경써야 할 조건은 두 가지였다.

• 합이 S 이상이어야 한다
• 수열의 길이가 가장 짧아야 한다

그래서 나는 누적합을 구하기로 했다. 만약 여지껏 수열의 합이 S보다 작다면, 계속해서 수를 더해나간다. 이때 더해가는 원소의 위치는 end로 잡는다.

 

그러다가 같거나 커지면 누적합에 더해나가는 것을 멈추고 start를 움직인다. 맨 앞의 원소부터 빼고 다시 크기를 비교한다. 물론 이때 수열의 길이도 따로 저장해둔다. 수열의 합 즉, 누적된 합이 S보다 작아질 때까지 맨 앞의 원소를 한 개씩 빼나간다. 

 

이 과정을 반복하다보면, 합이 S 이상이면서 길이가 가장 짧은 수열의 길이를 구할 수 있다. 이 작업을 위해 while문 안에 두 개의 while문을 작성했다.

 

원래 while문을 한 개만 썼는데, 마지막 원소까지 start로 탐색하기 위해서 while문을 두 개 쓸 수밖에 없었다.

 

그리고, 불가능한 경우에는 0을 출력해야 한다! 이 부분을 제대로 안 보고 풀어서 한 번 틀렸다.. 😊 

 

# Code

import java.io.*;
import java.util.StringTokenizer;
public 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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int min = Integer.parseInt(st.nextToken());
        int[] inputs = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0 ; i < N ; i++) {
            inputs[i] = Integer.parseInt(st.nextToken());
        }
        int ans = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        while (end < N) {
            while (end < N && sum < min) {
                sum += inputs[end];
                end++;
            }
            while (start < N && sum >= min) {
                ans = Math.min(ans, end - start);
                sum -= inputs[start];
                start++;
            }
        }
        if (ans == Integer.MAX_VALUE) ans = 0;
        System.out.println(ans);
    }
}

 

 

# 결과