[백준] 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
Author And Source
이 문제에 관하여([백준] 1806 부분합 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-1806-부분합-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)