[백준] 1806 부분합 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let n = Number(input[0].split(" ")[0]);
let m = Number(input[0].split(" ")[1]);
let left = (right = sum = 0);
let ans = Infinity;
let arr = input[1].split(" ").map(Number);
while (left <= right) {
  if (sum >= m) {
    ans = Math.min(ans, right - left);
    sum -= arr[left];
    left++;
  } else if (right == n) break;
  else {
    sum += arr[right];
    right++;
  }
}
if (ans !== Infinity) console.log(ans);
else console.log(0);

✔ 알고리즘 : 투포인터

💡 sum>=m이 되는 순간 구간합이 m 이상되는 구간이되므로 ans에 Math.min함수를 통하여 작은 구간의 길이를 저장하고 최소구간을 찾아야하므로 arr[left]값을 sum에서 빼고 left 포인터를 1증가시킴

✔ right 포인터가 n이 되면 구간끝까지 탐색한 것이므로 탐색종료

✔ sum<m 인 경우 right 포인터를 증가시키면서 sum값에 더해줌

✔ 난이도 : 백준 기준 골드4

좋은 웹페이지 즐겨찾기