Node.js) 백준 1806번: 부분합

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

1806번: 부분합

1. min(answer) 정하기 

우선 가장 짧은 길이를 원소의 개수+1 로 정해준다. 

만약 조건을 충족하는 연속하는 부분수열이 없을 경우 0을 출력하기 위함. 

 

2. 투포인터, 합 초기화

 시작 포인터 0, 끝 포인터 0에서 시작.   최초 합은 첫번째 원소의 값

 

3. 투포인터 반복 시작. start가 N과 같아지면  이미 모든 경우를 살폈으므로 종료. 

 

4-1, 합이 S보다 크거나 같다면 조건을 충족.

수열의 길이를 계산하고 min보다 작다면 업데이트.

sum에서 기존의 start 포인터가 가리키던 값을 빼고

start를 1 증가. 

 

 

4-2. 합이 S보다 작다면 

 end 1 증가.

end가 N이면 더이상 조건을 만족할 수 없으므로 종료

end가 N이 아니면 sum에 end 포인터가 가리키고 있는 값을 더함. 

 

 

 

const fs = require('fs');
const [a, b] = fs.readFileSync("./dev/stdin").toString().trim().split("\n")

const [N, S] = a.split(' ').map(v => +v);
const nums = b.split(' ').map(v => +v);

let start = 0;
let end = 0;
let sum = nums[0];
let answer = N + 1;
while (start < N) {
  if (sum >= S) {
    let temp = end - start + 1;
    if (answer > temp) answer = temp;
    sum -= nums[start];
    start++;
  } else {
    end++;
    if (end == N) {
      break;
    }
    sum += nums[end]
  }
}
if (answer == N + 1) console.log(0)
else console.log(answer)