[문제풀이] 백준 1806 - 부분합

📢 문제

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

📢 알고리즘

투포인터

📢 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  int N; //수열 길이
  int S; //최소 합
  cin >> N >> S;
  vector<int> arr(N); //수열

  //수열 입력받기
  for (int i = 0; i < N; i++)
  {
    cin >> arr[i];
  }

  int start = 0; //부분수열의 start index
  int end = 0; //부분수열의 end index
  long long sum = arr[0]; //부분수열의 합
  int minLen = N + 1; //부분수열의 최소 길이

  // S > sum이면 e++
  // S <= sum이면 minLen기록, s++

  while (start <= end && end < N)
  {
    if (sum >= S)
    {
      minLen = min(minLen, end - start + 1);
      sum -= arr[start];
      start++;
    }
    else
    { // sum < S
      end++;
      sum += arr[end];
    }
  }

  if (minLen > N)
  {
    cout << 0;
  }
  else
  {
    cout << minLen;
  }
}

• minLen = min(minLen, end - start + 1);

  • <algorithm>라이브러리의 min함수 사용해서 아래 코드를 간단하게 줄일 수 있음

  if(minLen > end - start + 1) {
     minLen = end - start + 1;
   }

• S > sum 이면

  • 새로운 수를 탐색해 포함시켜야 하므로 end++
  • sum은 arr[start] ~ arr[end+1]이 됨

• S <= sum 이면

  • 조건을 만족했으므로, 현재 부분수열의 길이가 minLen보다 짧을 경우 minLen 갱신
  • 최소 길이를 구해야 한다. 근데 이보다 더 짧은 길이로도(더 작은 합으로도) 조건을 만족할 수도 있으니 start++
  • sum은 arr[start+1] ~ arr[end]이 됨

• start == end(부분수열의 길이가 1)일 때 S <= sum을 만족한다면, start++가 수행되므로 다음번 while문 실행시 while문 조건에 위배되어 break

• 투포인터의 경우, for문으로 모든 경우를 돌기 보다는 while문 안에서 start와 end를 움직이는게 좀더 취지에 맞는듯..?

📖 참고자료
https://9967han.tistory.com/29