1806 부분합 골드4

🗒 문제 링크

풀이

문제에서 끄집어내야할 키워드는 우선 연속된 수들의 부분합,가장 짧은 부분합의 길이, S이상을 만들수 없으면 0 출력 정도라고 생각한다.

이에 따라 필요한 변수는 시작인덱스를 저장할 값, 해당 인덱스부터 시작해서 배열을 순회하며 더해진 부분합, 해당 부분합의 길이 이며 각각startIndex , curSum, curLength로 설정해주었다.

배열의 모든 요소를 시작인덱스로 하여 순회할수있도록
while문 안에 for문이 돌아가는 형태로 짜 주었고,for문을 조건을 크게 두가지로 주었다

1. 현재 부분합 (curSum)이 S 이상일 경우
	- 여기에서 answer값이 현재 부분합의 길이보다 클 경우 또는 answer값이 초기값 일경우 answer값을 현재 부분합으로 할당해주었다.
2. answer값이 0 (초기값일 경우를 제외해주기 위해)이 아니고,현재 부분합의 길이 (curLength)가 answer보다 클때

그리고 while문의 가장 마지막에서 조건문을 걸어주어 요소의 가장 마지막 값의 경우도 탐색해 주었다 (이 부분때문에 1차시도에서 실패했다)

⌨️ 코드

/*
    문제 이름 : 부분합
    문제 번호 : 1806
    문제 링크 : https://www.acmicpc.net/problem/1806
*/

const fs = require("fs");

// 백준 제출시 주석 제거
// const readFileSyncAddress = "/dev/stdin"

// VScode 테스트시 주석 제거
const readFileSyncAddress = "example.txt";

const input = fs
  .readFileSync(readFileSyncAddress)
  .toString()
  .trim()
  .split("\n");

const [N, S] = input[0].split(" ").map((item) => +item);
const arr = input[1].split(" ").map((item) => +item);

function solution(N, S, arr) {
  let answer = 0;
  //시작 인덱스
  let startIndex = 0;

  while (startIndex !== arr.length) {
	//현재 부분합의 길이
    let curlength = 0;
	// 부분합
    let curSum = 0;
    for (let i = startIndex; i < arr.length; i++) {
      if (S <= curSum) {
        if (answer > curlength || !answer) {
          answer = curlength;
        }
        break;
      }
      if (answer && curlength > answer) {
        break;
      }
      curSum += arr[i];
      curlength += 1;
    }
    startIndex += 1;
    if ((answer > curlength || !answer) && curSum >= S) {
      answer = curlength;
    }
  }

  console.log(answer);
}

solution(N, S, arr);