[백준1806] 부분합

yoontaeng·2022년 7월 19일

백준 알고리즘

📎 문제링크

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

📄 문제설명

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

입력

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

📝 문제풀이

sliding window 문제로 sum>=S 일때 low++, sum<S일때 ++high 의 알고리즘을 생각해서 풀면 된다. 즉 내가 목표로 하는 값과 같거나 이상일때는 low를 index로 하는 nums 값을 제거 함으로써 한칸 앞으로 가고 S보다 작으면 ++high의 인덱스 값을 추가함으로써 sliding window를 앞으로 이동시켜준다. 이때 high는 먼저 값을 상승시키는 것에 주의!!

💡 Code

코드

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

public class Main {
    static int N;// 수열 요소 개수
    static int S; // 목표 합
    static int[] nums;
    static int low,high;
    static int sum,min,answer;
    public static void main(String[] args) throws Exception {
     //알고리즘 문제 풀때는 exception을 하면 거의 모든 오류 던져줌
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N + 1]; // out of index 방지 N+1

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

        }
        low=0;high=0;sum=nums[0];min=0; answer=N+1;
         //sliding window - low,high 설정 high값이 N이 되면 전부 탐색이 끝난것
        //low 값이 있어야 초기 이전값을 순차적으로 제거하면서 오게 된다.
        while(true){
            //sum>=S 일때 low++
            if(sum>=S){
                min=high-low+1;
                if(min<answer){
                    answer=min;
                }
                sum-=nums[low++];
            }
            //sum<S일때 ++high
            else{
                sum+= nums[++high];
            }
             // 탈출 조건
            if(high==N){
                break;
            }
        }if(answer==(N+1)){  // 합을 만드는게 불가능할시 0 출력 
            System.out.println(0);
        }else {
            System.out.println(answer);
        }
    }
}

수정 코드(Math.min 추가)

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

public class Main {
    static int N;// 수열 요소 개수
    static int S; // 목표 합
    static int[] nums;
    static int low,high;
    static int sum,min,answer;
    public static void main(String[] args) throws Exception {
        //알고리즘 문제 풀때는 exception을 하면 거의 모든 오류 던져줌


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        nums = new int[N + 1]; // out of index 방지 N+1

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

        }
        low=0;high=0;sum=nums[0];min=N+1; 
        while(true){
            //sum>=S 일때 low++
            if(sum>=S){
               /* min=high-low+1;
                if(min<answer){
                    answer=min;
                }*/
                min=Math.min(high-low+1,min);
                sum-=nums[low++];
            }
            //sum<S일때 ++high
            else{
                sum+= nums[++high];
            }
             // 탈출 조건
            if(high==N){
                break;
            }
        }if(min==N+1){
            System.out.println(0);
        }else {
            System.out.println(min);
        }
    }
}