[백준] P1806 부분합

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

1806번: 부분합

 

🖊️문제

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

 

🖊️문제 풀이

부분합을 투포인터를 이용해 푸는 문제다. 

여태 풀었던 투포인터 문제들과 비교했을 때 조금 어렵게 느껴졌음...

 

배열 길이는 n이 아닌 n+1로 초기화해주었는데, 부분합을 구하는 과정에서 배열의 인덱스를 조정하면서 값을 구하게 된다. right가 배열의 마지막 인덱스에 도달했을 때, 포인터를 이동시키는 경우 인덱스가 n을 초과할 수 있기 때문에 n+1로 초기화해준 것이다.

 

left, right를 이용해 투포인터 알고리즘을 적용할 때 우선 이 둘은 0으로 초기화해두고 문제를 풀기위해 사용할 추가 변수 sum은 0, answer은 최솟값을 구해주기 위해서 큰 수 아무거나로 설정해주고 투포인터를 적용해줬다.

 

🖊️코드

package 투포인터;

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

public class P1806 {

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

    int n = Integer.parseInt(st.nextToken());
    int s = Integer.parseInt(st.nextToken());
    int[] arr = new int[n+1];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    int answer = Integer.MAX_VALUE;
    int left = 0;
    int right = 0;
    int sum = 0;
    while (left<=right && right<=n){
      if(sum < s){
        sum+=arr[right++];
      }else if(sum>=s && answer > right-left){
        answer = Math.min(answer, right-left);
      }else{
        sum-=arr[left++];
      }
    }

    System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);

  }

}