백준 1806 부분합

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

문제 설명

문제

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

입력

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

출력

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

---

문제 풀이

투 포인터 느낌으로 풀이 (i, startIndex)

for 문을 돌면서 sum 을 구하고 startIndex를 활용해 sum의 범위를 줄여 최소 길이를 구하기

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [n, s] = inputs[0].split(" ").map(Number);
const arr = inputs[1].split(" ").map(Number);

let startIndex = 0;
let answer = Infinity;
let sum = 0;

for (let i = 0; i < n; i++) {
  sum += arr[i];
  // startIndex를 줄여가면서 s보다 클 수 있는지 검사
  while (sum - arr[startIndex] >= s) {
    sum -= arr[startIndex];
    startIndex++;
  }
  // 더 짧은 길이 구하기
  if (sum >= s) {
    answer = Math.min(answer, i - startIndex + 1);
  }
}

console.log(answer === Infinity ? 0 : answer);

---

결론

누적합에 투 포인터 느낌을 적절히 사용하는 문제