[백준] 1806 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

2021-01-06

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main1806 {
    public static int N, S, arr[], answer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        
        answer = 987654321;
        int start = 0;
        int end = 0;
        int sum = 0;
 
        while(start < N) {
             if(sum >= S) {
                if(answer >= (end-start)) {
                    answer = end-start;
                }
                sum -= arr[start++];
            }else if(end == N) break; 
             else sum += arr[end++];
        }
        if(answer == 987654321) answer = 0;
        System.out.println(answer);
    }
}
 

 

#문제풀이

void2017.tistory.com/162

[백준] 2003 수들의 합2

앞서 풀었던 투 포인터 알고리즘을 이용한 문제에서 살짝 응용된 문제이다. 

 

같은 방법으로 이번엔 경우의 수를 구하는 것이 아니라 길이를 구하면 된다. 

 

+) 여기서 25%에서 계속 틀려서 도대체 원인이 뭘까 생각했는데 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

 

이 부분을 놓쳐서 생겼던 문제이다. 32번째 줄을 추가했더니 통과했다...